The Sevastopol base is the subject of an ongoing dispute between Moscow and Kiev. Ukraine wants the Russian base to leave the Crimea in 2017, while some senior Russian officials have controversially questioned the status of the port city, transferred from Russia to Ukraine by Nikita Khrushchev in the Soviet era.
Grigory Karasin told the Ogonyok magazine that Moscow "is ready to consider, on a constructive and flexible basis, various conditions for the further deployment of its fleet in Ukraine, paying maximum heed to Ukraine's interests in all spheres."
The diplomat said Russia was so far paying around $8 million a year in rent.
"Russia deducts the sum from Ukraine's state debt. This payment scheme expires in 2017," the deputy foreign minister said.
Frequent disputes have arisen of late between Russia and Ukraine over the lease of the Sevastopol base, as well as Kiev's plans to join NATO, which Moscow staunchly opposes.
The Crimea, now an autonomous region within Ukraine, is a predominantly Russian-speaking territory. Since the 1991 breakup of the Soviet Union, the Crimea has unsuccessfully sought independence from Ukraine.
