Ahead of a conference on the Ukraine crisis, Nato says it will reinforce its forces in eastern Europe, with “deployments at sea, in the air, on land” within days.
Nato Secretary General Anders Fogh Rasmussen told a news conference the organisation’s ambassadors had decided to take action “immediately”.
Nato fighter aircraft will fly more sorties over the Baltic region, allied ships will deploy to the Baltic Sea and the eastern Mediterranean, and military staff will be sent to improve preparedness and training.
He was speaking as tension between Russia and Ukraine increased following the arrival of pro-Russian militia in the town of Slaviansk.
They turned up in six Ukrainian armoured vehicles, decked with the Russian national flag and the banner of pro-Russian separatists.
The separatists said Ukrainian troops had handed over the vehicles after talks, but the Ukrainian defence ministry said they had been seized.
The development is significant amid fears that Russia, which western governments says has 40,000 troops massed on the border, may be considering an invasion of eastern Ukraine after annexing the Crimea. It is the deepest east-west crisis since the cold war.
Read more: International Editor Lindsey Hilsum blogs from eastern Ukraine on "Bread, not bullets".
The convoy, made up of masked men armed with Kalashnikov rifles, grenade launchers, knives and pistols, entered Slaviansk from the direction of Kramatorsk, where Ukrainian airborne troops seized back a military airfield on Tuesday.
Earlier, Ukrainian troops entered the centre of Kramatorsk, where they were blockaded by residents. Some of the armoured vehicles they used later ended up in Slaviansk.
In Donetsk, at least 20 armed separatists occupied the city council building, a spokeswoman for the council said. In the last week, pro-Russian activists have occupied public buildings in 10 eastern Ukrainian towns and cities.
The Ukrainian government says it is carrying out an “anti-terrorist” operation to protect its territory from what it sees as Russian aggression.
Russia accuses Ukraine of carrying out an unconstitutional coup to depose former president Viktor Yanukovych, who had close ties with Moscow, but denies orchestrating the occupation of buildings in Ukraine.
In a phone conversation with German Chancellor Angela Merkel, Russian President Vladimir Putin said Ukraine was “on the verge of civil war”.
Ukrainian Prime Minister Arseny Yatseniuk reacted by accusing Moscow of “exporting terrorism to Ukraine”.
The rival shows of strength precede talks on Thursday in Geneva, attended by Russia, Ukraine, the US and the EU.
Russia refuses to recognise the Ukrainian administration that replaced the Yanukovych presidency in February following days of anti-government protests in the Ukrainian capital Kiev.
Troops were not deployed during the protests, but police snipers shot dead dozens of demonstrators.
The US and EU accuse Moscow of orchestrating the separatist operation in eastern Ukraine as it did in Crimea before annexing the region in March following a referendum.
Russia is calling on Ukraine to accept a loose federal structure that respects the rights of Russian speakers.