In 1954 werd Sebastopol samen met de Krim overgedragen door de Russische deelrepubliek van de Sovjet-Unie aan de Oekraïense deelrepubliek. Wegens de aanwezigheid van de marinebasis werd Sebastopol in een aparte administratieve eenheid ingedeeld, los van de Krim, en stond de stad formeel onder rechtstreeks gezag van Kiev, maar werd ze feitelijk vanuit Moskou bestuurd.
Na het uiteenvallen van de [[SovjetunieSovjet-Unie]] hebben de pogingen van Oekraïne de Zwarte-Zeevloot van de oud-[[SovjetunieSovjet-Unie|USSR]] tot Oekraïens eigendom te verklaren tot spanningen geleid tussen Rusland en Oekraïne (overigens had Rusland datzelfde gedaan ten opzichte van de delen van de oud-Sovjetvloot die op het Russische grondgebied gestationeerd waren en Oekraïne voelde zich dan ook vrij naar het Russische voorbeeld te handelen). Ook hebben de aparte status van Sebastopol en de historische sentimenten die veel Russen koesteren jegens de stad erbij een grote rol gespeeld. Het Russische parlement, de [[Doema]], heeft zelfs een wet aangenomen waarin Sebastopol tot deel van het Russische grondgebied werd verklaard en heeft daarmee de spanningen hoog laten oplopen. Deze situatie werd opgelost in 1997 toen besloten werd tot de opdeling van de Zwarte-Zeevloot in het Oekraïense en het Russische deel. De Russen mochten tot 2017 een marinebasis in de stad huren. Daarmee schijnt Rusland te hebben toegegeven dat het Sebastopol als Oekraïens grondgebied beschouwt.
