Начало украино-российских отношений сразу же было омрачено заявлением пресс-секретаря российского президента Павла Вощанова о возможности пересмотра границ с новыми республиками — заявление было сделано сразу же после провозглашения Украиной декларации о независимости и вскоре дезавуировано высшей исполнительной властью России. Противоречия возникли при разделе Союза и создании Содружества независимых государств. Российское руководство рассматривало СНГ как способ сохранения своего политического влияния на территории бывшего СССР и даже, на начальном этапе, как средство восстановления Союза под руководством России. Для Украины это был наиболее приемлемый способ «цивилизованного развода» — она последовательно отклоняла все попытки России превратить СНГ в транснациональную структуру с функциями межгосударственного управления, продолжавшиеся до конца 1990-х годов. Фактически победила точка зрения Украины — роль СНГ в отношениях между бывшими республиками СССР постепенно уменьшалась, возрастало значение двусторонних и многосторонних договоров и связей (заметим, что тут Украину поддержало большинство других членов СНГ, кроме Беларуси и Казахстана). Точно так же падал престиж и значение СНГ в общественном сознании — если в 1994 г. 40 % опрошенных в Украине выступали за развитие отношений со странами СНГ, то в 1999 г. — только 15 %[93], и этот показатель падал и дальше.
Настоящим яблоком раздора стал Крым и связанная с ним проблема Севастополя и Черноморского флота — при этом как в России, так и в Украине по этим проблемам возникли разногласия между президентской и законодательной властью. В России парламент превратился в трибуну для пропаганды отделения Крыма от Украины и место паломничества крымских сепаратистов, в Украине левое большинство Верховной Рады заняло весьма двусмысленную позицию с точки зрения защиты территориальной целостности и суверенности Украины.
Наиболее острый конфликт разгорелся из-за Черноморского флота. Флот, состоявший из 440 кораблей, 18 субмарин, около 200 вспомогательных суден, 300 самолетов и 70 000 персонала, в свое время должен был обозначать стратегическое присутствие СССР в средиземноморском регионе. Поскольку флот был оснащен ядерным оружием, при создании СНГ было решено, что он будет находиться под совместным командованием Содружества. Украина была готова уступить ядерную часть флота СНГ, однако претендовала на половину остальных боевых кораблей, о чем и было заявлено в феврале 1992 г.
5 апреля 1992 г. Л. Кравчук издал указ о строительстве Вооруженных Сил Украины, которым предполагалось создание ВМФ Украины на базе Черноморского Флота, дислоцированного на территории страны. В ответ президент РФ Борис Ельцин поставил тот же флот под свое командование. Обстановка в Севастополе накалилась до предела. На улицах появились бронетранспортеры и патрули, оснащенные полным боекомплектом. Угроза открытого конфликта заставила обоих президентов через несколько дней приостановить действие указов. 23 июня в Дагомысе они договорились поставить флот в Крыму под совместное командование и к 1995 г. разделить его. 3 августа на встрече в Ялте была оговорена процедура раздела.