NATO expelled the pair, including Vassili Chizhov, son of Russias ambassador to the EU, in connection with an Estonian spy scandal which has already been through the courts, diplomats in the alliance said.
There was no official word from NATO, where a spokesman cited operational secrecy but Russias foreign ministry had no such qualms. A gross provocation has been carried out against two employees of Russias permanent office at NATO, whom the alliances security functionaries want to expel from Brussels on an absolutely invented pretext and without any distinct explanation, it said in a statement.
NATO diplomats named the other Russian official ordered to leave Moscows NATO mission as its chief counsellor to the alliance, Victor Kushakov.
The expulsions threaten to undermine a recent thaw in Russia-NATO relations, the ministry said, adding that unnamed forces opposed to improved ties were behind the incident.
Russias Ambassador to NATO Dmitry Rogozin hastily called a press conference in Brussels to warn that this is a very provocative action that cannot go without answer.
The spy row punctured the optimism generated when the two sides resumed formal talks at ambassador level, through the NATO-Russia council.
Adding to the rapid deterioration of relations, Russia vowed Thursday to defend the de facto borders of the two rebel regions and slammed upcoming NATO war games in Georgia as an overt provocation.
Russian President Dmitry Medvedev signed a pair of border defence treaties with the leaders of the Moscow-backed rebel regions of Abkhazia and South Ossetia at a Kremlin ceremony.
The planned NATO exercises in Georgia, no matter how one tries to convince us otherwise, are an overt provocation. One cannot carry out exercises in a place where there was just a war, Medvedev said.
Under the terms of the new treaties, Russia formally assumes responsibility for the border security of the two territories until Abkhazia and South Ossetia are ready to do so themselves.
Georgia shrugged off the pacts, saying the treaties only formalized a state of affairs in place since the end of last summers Russia-Georgia war.
However NATO spokesman James Appathurai charged that Eussia is in clear contravention of EU-brokered ceasefire agreements made with Georgia following their conflict last year.
He added that it was becoming increasingly difficult to match Russian rhetoric with reality on the ground, when it comes to Moscows criticism of planned NATO exercises in Georgia.