The Ukrainian president signed a decree ordering the Cabinet to draft by July 20 a law terminating all international agreements on the presence of Russia's Black Sea Fleet in Ukraine.
"The Russian side believes that it is premature to discuss terms for the fleet's presence. This topic should become the subject of a Russian-Ukrainian agreement and be considered in the context of bilateral relations," the ministry said.
Russia's Black Sea Fleet currently uses a range of naval facilities in the Crimea under an agreement signed in 1997, under which Ukraine agreed to lease naval facilities to Russia until 2017.
The May 16 resolution on measures to ensure Ukraine's status as a naval power, enacted by Viktor Yushchenko on May 20, was posted on his official website earlier Wednesday.
Disputes between Russia and Ukraine over the lease of the base are frequent. Russia currently pays $93 million per year to lease the base from its ex-Soviet neighbor, which is paid for with Russian energy supplies.
Ukraine's state security services barred Moscow Mayor Yury Luzhkov on May 12 from entering the former Soviet republic over his 'provocative' statements regarding the ownership of the Black Sea city of Sevastopol.
Moscow's mayor made strong calls for the disputed ownership of a Russian naval base in Sevastopol to be transferred back to Russia.
The head of the State Duma committee on CIS affairs, Alexei Ostrovsky, said in April that Russia could reclaim the Crimea if Ukraine was admitted to NATO. Media reported that President Vladimir Putin issued a similar threat at a closed-door speech to NATO leaders at the Bucharest Summit earlier this month.
Ukraine's Foreign Ministry confirmed last month that Russia had been invited to start talks in June on the withdrawal of its fleet from the Crimea, but said Moscow had yet to reply to the proposal.
