Однако ставший в сентябре 1991 года командующим Черноморским флотом адмирал И.В. Касатонов дал понять, что растаскивать флот он не позволит. Украинским активистам давали по рукам как в переносном, так и в прямом смысле. Тех, кто до решения вопроса на государственном уровне пытался принять украинскую присягу и вместе с ней объявить украинскими вверенные объекты, И.В. Касатонов по-флотски вежливо просил «выйти вон». Всего за несколько месяцев И.В. Касатонов довел официальный Киев до настоящей истерики. К сожалению, в Москве в тот момент думали о чем угодно, только не о государственных интересах страны. В результате дворцовых интриг в сентябре 1992 года, по настоянию украинской стороны, адмирал И.В. Касатонов был перемещен в Москву на должность первого заместителя Главнокомандующего ВМФ. При этом даже на этой должности его фактически отстранили от участия в решении вопросов по Черноморскому флоту, отправив в полугодовую командировку на Тихоокеанский флот.
5 апреля 1992 года президент Украины Л.М. Кравчук подписал указ «О переходе Черноморского флота в административное подчинение Министерству обороны Украины». В Севастополь была отправлена комиссия из высокопоставленных украинских военных для принятия под свой контроль всего флотского хозяйства. Для того чтобы иметь основания противостоять этой акции, нужен был аргумент не меньшей весомости. Об указе украинского президента в Севастополе узнали заранее и в спешном порядке приняли контрмеры. В Москву ушла депеша — нужен аналогичный указ Ельцина, в противном случае спустя несколько дней либо придется сдать флот, либо в Крыму может вспыхнуть самый настоящий вооруженный конфликт. Наконец-то и в Москве начали понимать, что Черноморский флот все же нужен России. 7 апреля 1992 года Б.Н. Ельцин в пику Киеву издал долгожданный указ «О переходе под юрисдикцию Российской Федерации Черноморского флота». Прибывшую в Севастополь украинскую делегацию ознакомили с указом Ельцина и дали понять, что пока президенты не договорятся между собой, никакого перехода флота под украинский контроль не будет.
«Война указов» завершилась в июне 1992 года, когда в Дагомысе Б.Н. Ельцин и Л.М. Кравчук подписали соглашение о дальнейшем развитии межгосударственных отношений, в котором указывалась необходимость продолжения переговорного процесса по созданию ВМФ России и ВМС Украины на базе Черноморского флота.
В августе 1992 года в Мухалатке близ Ялты состоялись российско-украинские переговоры на высшем уровне. Президенты России и Украины подписали соглашение о принципах формирования ВМФ России и ВМС Украины, на базе Черноморского флота бывшего СССР, согласно которому Черноморский флот становится Объединенным флотом России и Украины с объединенным командованием. Стороны договорились, что в течение трех лет вопрос о разделе Черноморского флота будет решен. Этот документ, однако, не прекратил попыток украинской стороны прибрать к рукам как можно больше кораблей и объектов, однако сделал эти случаи единичными и совсем уж нелегитимными. Однако захваты продолжились и провокации так же.
В сентябре 1993 года между Россией и Украиной была достигнута договоренность о том, что Черноморский флот получит возможность базироваться в Крыму. Официально решение о том, что главной базой Черноморского флота ВМФ России останется Севастополь, было принято в феврале 1995 года. Сказать, что переговорный процесс шел трудно, — значит, не сказать ничего. Доходило до форменного абсурда: однажды переговоры между министром обороны Украины В. Радецким и его российским коллегой П. Грачевым едва не сорвались из-за того, что табличка с именем российского министра оказалась… на два сантиметра больше, чем у украинского. Тот, разумеется, сразу же смертельно обиделся.
В начале лета 1995 года украинские власти решили захватить весь Черноморский флот. В июне 1995 года командир 17-й бригады спецназа военно-морских сил Украины А. Карпенко (и это после всех президентских договоренностей!) получил приказ захватить штаб Черноморского флота в Севастополе с применением оружия. По версии историка С. Козлова, в штаб бригады поступило боевое распоряжение о подготовке и выводе пятнадцати диверсионных групп в район базирования Черноморского флота, а также непосредственно в Севастополь. Одну из групп возглавил некий капитан 3-го ранга, которого Козлов знал как «Александра». Эта группа — в нее входили десять офицеров и мичманов — поступала в непосредственное распоряжение командующего ВМС Украины. Разведчики получили тротил (175 кг), заряды, магнитные мины, гранаты, вооружены они были автоматами Калашникова с приборами бесшумной и беспламенной стрельбы и бесшумными автоматическими пистолетами Стечкина.
Через месяц усиленной подготовки «Александр» получил распоряжение прибыть к командующему флотом Украины. Здесь, пишет дальше С. Козлов, «в присутствии группы старших офицеров и адмиралов „Александру“, не указывая пока сроков исполнения, поставили задачу подготовиться к захвату штаба Черноморского флота России и удержанию его до подхода главных сил».