The port is shared by both the Ukrainian and Russian naval forces . The city , formerly the home of the Russian then Soviet Black Sea Fleet , is now home to a Ukrainian naval base and a Russian naval base in facilities leased by the Russian Navy . The headquarters of both the Ukrainian Naval Forces and Russia 's Black Sea Fleet are located in the city .