После распада СССР между Россией и Украиной возник спор о разделе и базировании Черноморского флота (ЧФ). Окончательное урегулирование было достигнуто 28 мая 1997 года подписанием премьерами Виктором Черномырдиным и Павлом Лазаренко Соглашения о параметрах раздела ЧФ. В нем говорилось, что основная база ЧФ России находится в Севастополе. В ведение России также передавались 31-й испытательный центр в Феодосии, аэродром Гвардейское под Симферополем, военный санаторий и 830-й пост связи и ретрансляции в Ялте, 1001-й пункт высокочастотной связи в Судакском районе, 2436-й склад ракетного топлива на станции Мамут. Всего в Севастополе у российского флота 3570 зданий и сооружений, за его пределами — 1020. Статья 7 договора ограничивает численность обычных вооружений и техники России в Крыму 132 бронированными машинами, 24 единицами артиллерии калибра 100 мм и выше, 22 боевыми самолетами наземного базирования. В приложении №2 к договору указана предельная численность личного состава — 25 тыс. человек, включая 1987 человек в морской пехоте и морской авиации наземного базирования. Численность корабельного состава ограничена 388 кораблями и судами. В тот же день подписаны соглашения «О статусе и условиях пребывания ЧФ» и «О взаиморасчетах, связанных с разделом ЧФ и пребыванием ЧФ РФ на территории Украины». Предусматривалось, что Москва компенсирует Киеву стоимость полученных кораблей и судов на сумму $526,5 млн. Также определялись ежегодные платежи за использование флотом земли и объектов на сумму $97,75 млн путем уменьшения украинского госдолга.
21 апреля 2010 года в Харькове президенты Дмитрий Медведев и Виктор Янукович подписали Соглашение по вопросам пребывания ЧФ РФ на территории Украины. Оно предусматривает продление сроков базирования российского флота в Крыму еще на 25 лет после истечения 20-летнего срока действия договоров 1997 года в 2017 году, а также их возможное автоматическое продление на последующие пятилетние периоды. В документе оговорено, что c 2017 года плата за пребывание ЧФ в Крыму будет складываться из платежей России в размере $100 млн в год и дополнительных средств, получаемых за счет скидки Украине на российский газ в размере до $100 на 1 тыс. кубометров.