Russia and Ukraine found a way to solve some economic, political and military problems by agreeing to trade basing rights for cheap natural gas. Ukraine is dependent on Russia for natural gas supplies. Ukraine needs this gas to heat homes and businesses during the long Winters, and to operate many industrial enterprises. The new deal extends the Russian lease on their naval base at Sevastopol (on the Ukrainian coast) for 25 years (to 2042). Many Ukrainian politicians opposed the deal, but it will save Ukraine $2 billion this year alone. So the arrangement was voted into law. This enables the Ukrainian economy to resume growth, as long as the price of natural gas remains at a level that Ukraine can afford. Long term, many Ukrainians see the natural gas price as something the Russians will eventually use to conquer Ukraine once more.
The Russian Black Sea Fleet, which is based in Sevastopol, recently suffered a major blow when its only operational submarine, a 19 year old Kilo class boat, broke down at sea and limped back to port on partial power. The Black Sea Fleet is a pretty ragtag outfit, equipped with Cold War leftovers. A Kilo class sub was the youngest major ship there. Most of the fifteen major surface ships are in need of repair, or not able to leave port at all. Some of the twenty minesweepers and missile equipped patrol boats date from the 1990s, but for the most part, the Black Sea Fleet is a rest home for Cold War relics. The Black Sea fleet has been continually declining since the Soviet Union dissolved in 1991. That decline was the result of new countries (like Ukraine and Georgia) inheriting old Soviet ships and bases. That was the dissolution deal. Wherever Soviet weapons or bases were normally were, belonged to one of the 14 new nations. Most of Russias high seas ships were based in northern Russia (the Northern fleet, based next to Finland and Norway) or the Far East (the Pacific fleet, based north of China and North Korea). But the Baltic and Black Sea fleets were largely based in ports that were now part of a foreign nation. Despite this, last year the Russian government ordered the navy to concentrate on building new ships for the Black and Baltic Seas, instead of planning a high seas aircraft carrier fleet.
In the 1990s, Russia negotiated a lease on their large naval base in Sevastopol, but the Ukrainians were determined to not renew the lease (due to expire in 2017). So Russia began building a new base to the east, on the Russian Black Sea coast. That effort may now be halted or cut back.
For over a century, Russia had four fleets (Northern, Pacific, Baltic and Black Sea). The latter two were virtually destroyed by the dissolution. But now Russia is having political problems (largely caused by Russia) with Georgia and Ukraine, and could really use some additional (and modern) naval power. To a lesser extent, the same situation applies in the Baltic (where Estonia, Latvia and Lithuania harbored, and often built, many of the Soviet ships of the Baltic fleet.) Poland, while not part of the Soviet Union, was a major naval ally, as was East Germany. Thus the Baltic fleet is a fraction of what it once was, and needs rebuilding.
With its main Black Sea base secure for over three decades, Russia appears determined to rebuild the fleet there, which also operates in the Mediterranean.