Central powers in Kiev are threatening Crimean authorities with reprisals if "provocations" against Ukrainian troops on the peninsula continue.
It comes after Russian troops seized control of Ukraine's Crimean naval base and raised the Russian flag.
The tense but peaceful takeover of the Ukrainian naval headquarters in the Black Sea port of Sevastopol signalled Moscow's intent to neutralise any armed opposition.
Russian soldiers, and so-called self-defence units of mainly unarmed volunteers who are supporting them across the peninsula moved in early in the morning and quickly took control.
Ukrainian military spokesman Vladislav Seleznyov said the commander of the Ukrainian navy, Admiral Serhiy Haiduk, was driven away by what appeared to be Russian special forces.
Russian Defence Minister Sergei Shoigu has now asked the authorities in Crimea to free Haiduk and allow him safe passage out of the region, the ministry said on Thursday (local time).
In Kiev, acting President Oleksander Turchinov threatened to take action if pressure on Ukrainian forces in Crimea did not stop.
"If by 2100 all provocations against Ukrainian troops have not stopped and Admiral Haiduk and all other hostages ... are not released, the authorities will take appropriate measures, including of a technical and technological nature," he said in a statement posted online.
Most of Crimea's electricity, water and food is supplied from the Ukrainian mainland and Turchinov's comments suggest Kiev could be prepared to squeeze the supplies.
"The Russian military is cynically refusing to negotiate ending the provocations and releasing the hostages," Turchinov said.
Russia's Itar-Tass news agency reported that Alexander Vitko, commander of Russia's Black Sea Fleet which is based in Sevastopol, had been involved in talks at the headquarters.
Shortly after the takeover of the base, Ukraine's acting Defence Minister Ihor Tenyukh said in Kiev that the country's forces would not withdraw from Crimea even though Russian President Vladimir Putin has signed a treaty to make it part of Russia.
But an hour later, Ukrainian servicemen, unarmed and in civilian clothing, began walking out of the headquarters. Within a few minutes a handful of troops in Ukrainian uniform, looking shell-shocked at the dramatic turn of events, followed suit.
PROTECTION FROM 'FASCISTS'
Later, pro-Western Ukrainian Prime Minister Arseniy Yatsenyuk ordered his first deputy prime minister and acting defence minister Tenyukh to fly to Crimea to "resolve the situation".
But Sergei Askyonov, Crimea's new prime minister since the Russian takeover, said Vitaly Yarema and Tenyukh would not be permitted to land.
Thousands of Russian soldiers took control of Crimea in the buildup to a weekend referendum last weekend in which the region, with ethnic Russians in the majority, voted overwhelmingly to leave Ukraine and join Moscow.
Putin said his move to take control of Crimea was justified by what he calls "fascists" in Kiev who overthrew pro-Moscow president Viktor Yanukovich last month after three months of violent street protests.
Ukraine and Western governments have dismissed the referendum as a sham, and say there is no justification for Putin's actions.
Moscow officially denies deploying extra troops and Russian soldiers in the region are wearing unmarked uniforms, making it difficult to verify exactly who is who on the ground.
Ukraine's security chief says that the country will hold joint military exercises with the United States and Britain.
Andriy Parubiy, the secretary of the National Security and Defense Council secretary, said Ukraine would hold manoeuvres with the countries that signed the 1994 Budapest Memorandum. He didn't give any specifics.
The document was signed by the US, Britain and Russia to guarantee Ukraine's territorial integrity after it had surrendered its share of Soviet nuclear arsenals to Russia.
Ukraine has accused Russia of breaching the agreement by taking over the Crimean peninsula.
Ukrainian navy commander Serhiy Haiduk and several other hostages detained by Crimean authorities on Wednesday have been released, the Ukrainian presidential website said on Thursday.
A Ukrainian military spokesman said Admiral Serhiy Haiduk had been driven away from a navy compound in Russian-controlled Crimea by what appeared to be Russian special forces.
Russian Defence Minister Sergei Shoigu asked the authorities in Crimea on Thursday to free the detained hostages and allow them safe passage out of the region.