В октябре 1991 года Верховный Совет Украины принял решение о подчинении Украине Черноморского флота. 5 апреля 1992 года президент Украины Леонид Кравчук подписал Указ «О переходе Черноморского флота в административное подчинение Министерству обороны Украины».

7 апреля 1992 года президент Российской Федерации Борис Ельцин издал Указ «О переходе под юрисдикцию Российской Федерации Черноморского флота».

«Война указов» завершилась встречей 23 июня 1992 года в Дагомысе Бориса Ельцина и Леонида Кравчука. Подписано соглашение о дальнейшем развитии межгосударственных отношений, в котором указывается на необходимость продолжения переговорного процесса по созданию ВМФ России и ВМС Украины на базе Черноморского флота.

3 августа 1992 года в Мухалатке близ Ялты состоялись российско-украинские переговоры на высшем уровне. Президенты России и Украины подписали соглашение о принципах формирования ВМФ России и ВМС Украины на базе Черноморского флота бывшего СССР, согласно которому Черноморский флот становится Объединенным флотом России и Украины с объединенным командованием. Стороны договорились, что в течение трех лет вопрос о разделе Черноморского флота будет решен.

17 июня 1993 года в Подмосковье состоялись переговоры Бориса Ельцина и Леонида Кравчука. Подписано соглашение о формировании флотов двух государств на базе Черноморского флота.

3 сентября 1993 года в Массандре (Крым) на рабочей встрече президентов России и Украины подписан протокол, в соответствии с которым Черноморский флот со всей его инфраструктурой в Крыму будет использоваться Россией.

15 апреля 1994 года в Москве президенты России и Украины подписали соглашение о поэтапном урегулировании проблемы Черноморского флота, по которому ВМС Украины и Черноморский флот РФ базируются раздельно. В соответствии с соглашением Украине должно перейти до 20% судов ЧФ.

7-8 февраля 1995 года в Киеве была достигнута договоренность о базировании Черноморского флота России в Севастополе.

9 июня 1995 года в Сочи состоялась встреча Бориса Ельцина и нового президента Украины Леонида Кучмы. Подписано соглашение, согласно которому Черноморский флот России и Военно-морские силы Украины базируются раздельно; основная база и штаб флота находятся в городе Севастополь; имущественные вопросы должны быть урегулированы с учетом ранее достигнутой договоренности о разделе имущества пополам. России передается 81,7%, Украине — 18,3% судов.

28 мая 1997 года в Киеве были подписаны межправительственные соглашения о статусе и условиях пребывания Черноморского флота России на территории Украины, о параметрах деления ЧФ, о взаиморасчетах, связанных с разделом флота и пребыванием Черноморского флота РФ на украинской территории. Украинский парламент ратифицировал эти документы 24 марта 1999 года. Государственная Дума ратифицировала 18 июня 1999 года.

В соответствии с достигнутыми договоренностями (от 9 июня 1995 года и 28 мая 1997 года) Черноморский флот России будет состоять из 338 кораблей и судов, 106 летательных аппаратов. Численный состав — 25 тыс. человек. За Россией осталось 3 пункта базирования корабельного состава: Севастополь (бухты Севастопольская, Южная, Карантинная, Казачья), Феодосия и временно Николаев; 2 основных аэродрома: Гвардейское, Севастополь (Кача); 2 запасных аэродрома: Севастополь (мыс Херсонес, Южный); 1 место дислокации береговых войск: Севастополь.

К концу мая 1996 года украинской стороне отошло 7 из 10 пунктов базирования корабельного состава: Измаил, Одесса, Очаков, Черноморская, Новоозерное, Балаклава, Керчь; 4 из 6 основных аэродромов: Лиманское, Веселое, Октябрьское, Мирный; 5 из 7 запасных аэродромов: Геническ, Сокологорное, Большой Токмак, Воинка, Сизовка; 4 из 5 мест дислокации береговых войск: Симферополь, Евпатория, Перевальное, Межгорье.

Бухта Стрелецкая планируется к совместному использованию флотами двух стран.