Armed men without identifying insignia blocked the road to Crimea's Sevastopol airport, taking control of the facility. Gunmen also guarded Crimea's parliament building as the region's prime minister called upon Russia to help keep peace. Photo: AP

Russia's parliament voted unanimously on Saturday to approve a request from President Vladimir Putin to deploy troops in Ukraine, defying warnings from U.S. President Barack Obama and other Western leaders not to intervene.

Russian lawmakers also asked Mr. Putin to recall the country's ambassador to the U.S. Mr. Obama has publicly warned Russia that there would be costs for any military intervention in Ukraine.

Saturday's move comes as Russian troops and their local allies have already largely taken control of Crimea, a restive province of Ukraine that belonged to Russia until 1954 and remains predominantly pro-Russian.

Following the vote in Moscow, Western officials expressed alarm and cautioned Russia to respect Ukraine's territorial integrity.

"I deplore today's decision by Russia on the use of armed forces in Ukraine. This is an unwarranted escalation of tensions," said European Union foreign-policy chief Catherine Ashton.

United Nations Secretary-General Ban Ki-moon said he is "gravely concerned about the deterioration of the situation" in Ukraine.

U.S. Defense Secretary Chuck Hagel spoke to his Russian counterpart, Sergei Shoigu, after the vote. U.S. defense officials wouldn't immediately provide any details of the call and didn't say whether Mr. Hagel delivered any warning or caution.

Meanwhile, skirmishes broke out in other regions of Ukraine, raising concern about broader unrest.

The new government in Kiev called an urgent session of its security council Saturday evening and set a special parliamentary meeting for Sunday to discuss the Russian move.

Vitali Klitschko, the former boxing champion who is one of the protest movement's most prominent leaders, called on parliament to call a "general mobilization" to respond to the threat, apparently referring to Ukraine's military.

Heavily armed troops, many from Russia's Black Sea Fleet, which is based in the Crimean port of Sevastopol, surrounded key facilities across the region in the past day. The newly installed pro-Russian leader of Crimea Saturday formally asked Russia to deploy its troops to help secure the region.

Mr. Putin's request didn't specify how many troops might be sent. It said they would be deployed "until the normalization of the social-political situation in the country."

The request cited the "threat to the lives of Russian citizens" living in Crimea, as well as the personnel of the Black Sea Fleet.

The approval of Mr. Putin's request doesn't necessarily mean troops will be dispatched immediately, an official said.

"Having the right (to deploy forces) doesn't mean immediately, momentarily exercising that. So we will hope that the situation will go according to a better scenario and won't continue to be exacerbated as it is now," presidential spokesman Dmitry Peskov said in a radio interview.

Anti-Yanukovych protesters sing Ukraine's national anthem in Kiev's Independence Square, Saturday. Associated Press

Mr. Peskov said in the interview that no decision had been made yet on deploying forces to Ukraine or on recall of the ambassador.

Sergei Aksyonov, who was appointed prime minister of Crimea after armed men took over the regional parliament this week, said troops from the Black Sea Fleet are guarding vital facilities in the region and helping with patrols to ensure public order. Mr. Aksyonov, who is pro-Russian, said he was taking command of the peninsula's police and army.

In the economically important eastern Ukrainian city of Donetsk, hundreds of pro-Russian protesters massed Saturday in the main square and took over a main government administration building, and raised the Russian flag, according to local residents and news outlets. It was unclear whether the protesters were local residents. The number of protesters was also unclear; Russian and Ukrainian media had wildly different estimates of crowd strength.

The Donetsk city council issued a statement demanding a referendum over whether the mining region with strong ties to Russia should remain part of Ukraine.

By nightfall, the area around the Donetsk main square was quiet. A reporter from Ukrainian national television said that the protesters remained inside the building, drinking tea and planning new pro-Russia protests for Monday.

In Kharkiv, protests erupted Saturday between crowds of mostly young men who have been camped out at different sides of the city's main square—Europe's largest city square—for weeks now.

The groups, one which is pro-Kiev and the other which is pro-Moscow, are mostly local youth, some of which are supporters of the local football team, who appear to have more personal grievances with each other rather than deeply held political agendas, according to local residents who know several of the people at the demonstration.

Interfax reported that about 100 people were injured in the disorder Saturday, though that figure couldn't immediately be confirmed.

Ukraine military bases were quickly surrounded and sealed off Saturday by Russian forces in Crimea as the Kremlin made preparations for a larger-scale landing of troops.

Russian troops were posted near the gates and around the perimeters of several bases near Sevastopol. When asked why they were there, officers replied that they were providing security to the bases, to stop any pro-Russian citizens who might try to take them.

The troops posted around the base had no markings on their uniforms. Their commander, when asked if he could reveal their nationality, said "of course not." Others admitted they were Russian. Ukrainian officials at the base said the Russians were allowing food and provisions to be brought in.

Russia's Foreign Ministry accused the government in Kiev of trying to destabilize the region and directing gunmen to capture Crimea's ministry of internal affairs building overnight. It said the attack, which couldn't be verified, was averted with "decisive action."

Five people who live in the buildings next to the ministry building in Simferopol said everything was peaceful Friday night and they heard nothing. There were no signs of struggle at the building complex.

Vladimir Krashevsky, a top official at the Simferopol-based division of the local berkut, or riot police, said there was no attack by Kiev-allied gunmen on the building, where he gave an impromptu news conference Saturday.

"There was no attack here and there won't be one," he said.

The resolution authorizing the use of force in Ukraine cited the threat to Russian citizens there, but officials in Moscow repeatedly suggested that the Kremlin was coming to the defense of ethnic Russians in Ukraine, even if they hold Ukrainian citizenship.

"There's a threat today to the lives and safety of our fellow citizens, of Russian speakers, of ethnic Russians," Valentina Matvienko, speaker of the upper house of parliament, told reporters after the vote. "We can't remain indifferent."

A local man tells WSJ's Alan Cullison the reasons behind his decision to block access to Sevastopol airport in the pro-Russian region of Crimea.

Asked about possible western counter-intervention, she said there was no ground for it. "With all due respect to the United States, where is the U.S. located and where is Russia? This is happening on Russia's border."

Alexander Chekalin, a senator, spoke before the vote, saying, "we are one people, speaking one language, following one faith and sharing one history." The eastern and southern parts of Ukraine have a large number of Russian-speakers who are members of the Orthodox church.

Friday, armed men surrounded Crimea's two main airports, took command of its state television network and set up checkpoints along the key roads connecting the peninsula to the rest of Ukraine. On Saturday, professional military men in unmarked green camouflage uniforms appeared outside the Crimean parliament building in Simferopol.

Ukrainian officials said the well-equipped men—many of whom carried sophisticated automatic weapons—were Russian soldiers.

The leader of the Crimean Tatars, the ethnic minority that accounts for 12% of Crimea and supports the new government in Kiev, sought to dispel the notion that the seizure of government buildings in Crimea had grown out of a citizen uprising.

"These buildings were seized by specially trained people acting on military orders," said Refat Chubarov, the Tatar leader and deputy in the parliament, at a news conference Saturday.

Ukraine's new prime minister, Arseniy Yatsenyuk, called the continuing militarization in Crimea a provocation intended to draw in Ukraine militarily. He demanded Russian forces return to their base in Sevastopol.

"The presence of Russian troops is nothing more than a violation of the agreement for the Black Sea Fleet to be in Ukraine," Russia's Interfax news agency quoted him as saying. "We urge the Russian government to withdraw their troops and return them to their base."

—James Marson and Alexander Kolyandr in Kiev contributed to this article.

Crimea's Challenge

Ukraine's Crimea region has become the flashpoint for a backlash against the pro-Western protesters that drove President Viktor Yanukovych from power. View the interactive.