Unatoč navedenom, tenzije se nisu smanjile. Gradonačelnik Moskve poveo je kampanju za polaganje prava na grad Sevastopolj u kojem je bila smještena flota, a nju je u prosincu 1996. potvrdilo Vijeće Ruske Federacije. Potaknuta tim teritorijalnim zahtjevima, Ukrajina je u siječnju 1997. predložila "posebno partnerstvo" s NATO-om. Ipak, 28. svibnja 1997. Ruska Federacija i Ukrajina sklapaju nekoliko sporazuma vezanih uz flotu i pomorska postrojenja na Krimu: Sporazum o parametrima podjele Crnomorske flote, Sporazum o statusu i uvjetima boravka Crnomorske flote Ruske Federacije na teritoriju Ukrajine i Sporazum Vlada Ruske Federacije i Ukrajine o plaćanjima povezanim s podjelom Crnomorske flote i njezinu boravku na teritoriju Ukrajine.

Ukratko, sporazumima Sovjetska Crnomorska flota¹ sa zapovjedništvom na poluotoku Krimu, u to doba podijeljena je između Rusije i Ukrajine u odnosu 81,7 % za Rusiju naspram 18,3 % za Ukrajinu. Na ime takvog načina podjele dogovoreno je da će Rusija na ime naknade za udio platiti 526 milijuna dolara. Ukrajina je, s druge strane, dopustila Rusiji zakup pomorskih postrojenja na Krimu na 20 godina, do 2017., s mogućnošću obnove ugovora nakon pet godina, a cijena zakupa iznosila je 97 milijuna dolara godišnje. Iznos zakupa umanjen je za opskrbu Ukrajine ruskim gorivom. Pravila o stacioniranju ruske Crnomorske flote uređena su Sporazumom o statusu i uvjetima boravka ruske Crnomorske flote na teritoriju Ukrajine prema kojem su Rusi na Krimu mogli držati do 25.000 trupa, 24 artiljerijska sustava, 132 borbena oklopna vozila i 22 vojna zrakoplova. Zauzvrat, Rusija je bila dužna poštovati suverenitet Ukrajine, poštovati njezino zakonodavstvo i ne miješati se u unutarnje stvari Ukrajine. Rusko vojno osoblje bilo je dužno pokazati svoje vojne iskaznice prilikom prelaska rusko-ukrajinske granice, a ruske snage mogle su djelovati izvan označenih mjesta samo u koordinaciji s nadležnim ukrajinskim institucijama. Nadalje, prema Sporazumu², ruska strana bila je dužna odmah informirati ukrajinsku stranu o imenovanju zapovjednika Flote; ukupan broj osoblja, brodova, oružja i vojne opreme Crnomorske flote nije smio ići izvan parametara utvrđenih Sporazumom o parametrima podjele; ruska strana obvezala se da Crnomorska flota neće imati nuklearno oružje koje je locirano na teritoriju Ukrajine; u slučaju da ruska strana pokrene izgradnju putova, mostova, zgrada na prostoru zakupa, to je dužna učiniti u suradnji s ukrajinskim vlastima i dr.

Nakon tih sporazuma, godine 2010., neočekivano i u tajnosti potpisan je Kharkivski pakt kojim je zakup produljen do 2042. godine, s mogućnošću obnove za dodatnih pet godina u zamjenu za višegodišnji ugovor o povoljnim cijenama za opskrbu Ukrajine prirodnim plinom. Politički gledano, Rusija je tim paktom osigurala nepristupanje Ukrajine NATO-u čija Povelja priječi zemlje članice da imaju vojne baze na svom teritoriju. Nakon aneksije Krima, 2014., ruski predsjednik Vladimir Putin predložio je raskid svih sporazuma, uključujući i Kharkivski pakt, što je Državna Duma prihvatila.

U travnju 2023., ukrajinski Ustavni sud odlučio je raspravljati o ustavnosti Kharkivskog pakta nakon zahtjeva 49 članova ukrajinskog parlamenta.