Питання Криму та Чорноморського флоту (ЧФ) було одним з найбільш конфліктогенних в історії українсько-російських відносин новітньої доби. Після розпаду СРСР, за оцінками міжнародних експертів, вартість ЧФ становила 80 млрд доларів США. Розподіл за принципом 50 на 50 не влаштовував російських керманичів. З метою вирішити питання ЧФ на свою користь РФ вдалася до «газового шантажу» — Україні було відверто запропоновано погасити борг за поставки газу своєю часткою флоту, а в разі несплати Росія погрожувала припинити постачання газу.
Переговорний процес розтягнувся на довгих п'ять років і завершився підписанням прем'єр-міністрами України та Росії 28 травня 1997 року «Угоди між Урядом України і Урядом Російської Федерації про взаємні розрахунки, пов'язані з розподілом Чорноморського флоту та перебуванням Чорноморського флоту Російської Федерації на території України». Згідно досягнутим домовленостям флотське майно було поділено порівну, а от 80% плавзасобів відійшло на користь Росії. Також було погоджено, що штаб та основна база ЧФ РФ буде перебувати у Севастополі до 2017 року.
Збереження присутності російського флоту в Україні було важливим геополітичним завдання для російського керівництва, особливо після перемоги на президентських виборах 2004 року проєвропейського кандидата Віктора Ющенка, який взяв курс на вступ України до НАТО. Реалізація російських прагнень втримати Україну в орбіті свого впливу стала можливою після зміни владних еліт в Україні. Додатковим інструментом тиску на Україну став контракт між НАК «Нафтогаз України» та ВАТ «Газпром», підписаний 19 січня 2009 року в умовах російського газового шантажу: він встановлював для України світову ціну у 400 доларів США за 1 тисячу кубометрів газу.
Після перемоги Віктора Януковича на президентських виборах 2010 року попередній уряд, очолюваний Юлією Тимошенко, був відправлений у відставку, в парламенті була створена пропрезидентська коаліція «Стабільність і Реформи», яка 11 березня підтримала призначення прем'єр-міністром представника партії регіонів Миколи Азарова. Зі зміною політичної влади в Україні розпочався новий етап зближення з Росією, одним з перших кроків на шляху реалізації якого стало укладення 21 квітня 2010 року у Харкові «Угоди між Україною і Російською Федерацією з питань перебування Чорноморського флоту Російської Федерації на території України», підписаної Президентом України Віктором Януковичем і президентом РФ Дмитром Мєдвєдєвим.
Згідно з досягнутими домовленостями, термін перебування ЧФ РФ в Севастополі був подовжений до 28 травня 2042 року і передбачав його автоматичну пролонгацію щоп'ять років при відсутності заперечень котроїсь зі сторін, оплата Україні за перебування ЧФ РФ встановлювалась у розмірі 100 млн доларів США на рік, починаючи з 2017 року, і додаткової знижки на постачання газу за контрактом 2009 року між «Нафтогазом» та «Газпромом» у розмірі 30% (але не вище 100 доларів) з моменту набуття чинності «Угоди». Крім того, Янукович і Мєдвєдєв підписали договір про будівництво моста через Керченську протоку, який мав бути зведений до 2014 року.
Опозиція та проєвропейськи налаштована громадськість звинуватила Януковича у здачі українських національних інтересів, але 27 квітня 2010 року 236-а голосами Верховна Рада України проголосувала закон «Про ратифікацію Угоди між Україною та Російською Федерацією з питань перебування Чорноморського флоту Російської Федерації на території України»: у повному складі її підтримали депутати від Партії регіонів, Компартії, блоку Литвина-Тігіпка, більшість позафракційних депутатів та ряд парламентарів з опозиційних фракцій блоків Юлії Тимошенко і «Наша Україна — Народна самооборона».
Через два тижні після анексії Криму, Державна Дума РФ денонсувала три україно-російські угоди 1997 року, що стосувались параметрів поділу Чорноморського флоту, статусу його перебування в Україні, взаєморозрахунків з цього питання, і «Харківську угоду» 2010 року. 1 квітня 2014 року відповідний закон був схвалений Радою Федерації РФ і наступного дня підписаний Президентом РФ Владіміром Путіним.
В Україні, попри російську агресію у Криму і на Сході, «Харківська угода» денонсована не була з огляду на те, що, за словами міністра юстиції Павла Петренка, вони є «доказовою базою для підтвердження прав України в судах, в тому числі і прав на компенсацію збитків з боку Російської Федерації».