В сентябре 1993 года между Россией и Украиной была достигнута договоренность о том, что Черноморский флот получит возможность базироваться в Крыму. Официально решение о том, что главной базой Черноморского флота ВМФ России останется Севастополь, было принято в феврале 1995 года. Сказать, что переговорный процесс шел трудно, — значит, не сказать ничего. Доходило до форменного абсурда: однажды переговоры между министром обороны Украины В. Радецким и его российским коллегой П. Грачевым едва не сорвались из-за того, что табличка с именем российского министра оказалась… на два сантиметра больше, чем у украинского. Тот, разумеется, сразу же смертельно обиделся.

В начале лета 1995 года украинские власти решили захватить весь Черноморский флот. В июне 1995 года командир 17-й бригады спецназа военно-морских сил Украины А. Карпенко (и это после всех президентских договоренностей!) получил приказ захватить штаб Черноморского флота в Севастополе с применением оружия. По версии историка С. Козлова, в штаб бригады поступило боевое распоряжение о подготовке и выводе пятнадцати диверсионных групп в район базирования Черноморского флота, а также непосредственно в Севастополь. Одну из групп возглавил некий капитан 3-го ранга, которого Козлов знал как «Александра». Эта группа — в нее входили десять офицеров и мичманов — поступала в непосредственное распоряжение командующего ВМС Украины. Разведчики получили тротил (175 кг), заряды, магнитные мины, гранаты, вооружены они были автоматами Калашникова с приборами бесшумной и беспламенной стрельбы и бесшумными автоматическими пистолетами Стечкина.

Через месяц усиленной подготовки «Александр» получил распоряжение прибыть к командующему флотом Украины. Здесь, пишет дальше С. Козлов, «в присутствии группы старших офицеров и адмиралов „Александру“, не указывая пока сроков исполнения, поставили задачу подготовиться к захвату штаба Черноморского флота России и удержанию его до подхода главных сил».

Но российская контрразведка сработала на опережение. В штабе Черноморского флота знали о готовящейся операции по захвату штаба с минированием кораблей. Офицеры штаба спали у себя в кабинетах с оружием. 810-я бригада морской пехоты России была готова вывести на улицы Севастополя бронетанковую технику. Однако командование Черноморского флота решило кончить дело миром. Хотя политически было целесообразно дать возможность 17-й бригаде пустить в ход оружие, а затем, показав это на весь мир по телевидению, потребовать вывода всех самостийных сил из Крыма с последующим общекрымским референдумом о статусе полуострова. Разумеется, последнее нужно было провести в присутствии наблюдателей из ОБСЕ, Турции и Киева. Но Ельцин пошел по пути капитуляции. 9 июня 1995 года президенты России и Украины снова встретились в Сочи, где подписали договор по Черноморскому флоту.

В соответствии с договором флот России должен был получить 81,7% кораблей и судов флота, а ВМС Украины — 18,3% соответственно. Раздел флотского имущества предлагалось вести по состоянию на 3 августа 1993 года, что было крайне невыгодно для России. В договоре особо подчеркивалось, что Черноморский флот Российской Федерации и ВМС Украины базируются раздельно.

23—25 ноября 1995 года в Сочи состоялась рабочая встреча министров обороны РФ и Украины, на которой подписано 17 соглашений и протоколов, по которым ЧФ теряет Мирный, Керчь, Новоозерный, Симферополь, Октябрьское. Все военные объекты, расположенных в этих местах дислокации, в полном объеме до 31 декабря 1995 года передаются Украине. Черноморский флот продолжает базироваться в Севастополе, Феодосии, п.