Rusia a admis, lucru rar întâlnit la Moscova, că a încălcat legile ucrainene când a încercat să transporte rachete de croazieră în afara bazei navale ruseşti Sevastopol de la Marea Neagră.
În cursul lunii iulie, poliţia ucraineană a blocat plecarea din bază a un convoi de camioane militare ruseşti încărcate cu rachete, prin oraşul ucrainean Sevastopol, incident ce a deteriorat şi mai mult relaţiile, deja tensionate, dintre cele două foste republici sovietice. "Ne-a fost adus la cunoştinţă că s-au înregistrat încălcări ale acordurilor de bază privind Flota rusă a Mării Negre de la Sevastopol (...) În opinia noastră, încălcările sunt grave. Cei vinovaţi vor fi aspru pedepsiţi", a declarat comandantul naval, amiralul rus Vladimir Vâsoţki, citat de RIA Novosti.
Aflat duminică la Sevastopol pentru a celebra Ziua Marinei,Vâsoţki a recunoscut că documentaţia necesară aprobării (de către partea ucraineană a) deplasării convoiului (în afara bazei ruseşti) nu a fost întocmită corespunzător.
Moscova deţine cu chirie o bază pentru Flota Mării Negre la Sevastopol, port al peninsulei Crimeea, populată în principal de etnici ruşi. Statutul bazei a fost un măr al discordiei în relaţiile ruso-ucrainene încă de la independenţa Ucrainei în 1991.
Ucraina, care s-a angajat pe traiectoria strângerii relaţiilor cu Occidentul şi al cărei preşedinte, Viktor Iuşcenko, presează NATO pentru admiterea ţării sale în Alianţa Nord-Atlantică, vrea ca Rusia să-şi închidă baza navală de pe teritoriul ucrainean în 2017, la data expirării acordurilor existente.
Rusia consideră extinderea graniţelor NATO către frontierele sale drept o ameninţare la propria securitate şi s-a simţit deranjată de exerciţiile comune Ucraina-NATO de la sfârşitul lui iulie 2008 din Marea Neagră. Luna următoare tensiunile bilaterale au crescut din nou, când Rusia şi-a trimis navele de luptă de la baza din Sevastopol împotriva statului caucazian ex-sovietic Georgia, în timpul războiului ruso-georgian de cinci zile (7 - 12 august 2008). Iuşcenko a sprijinit Georgia în acest conflict.
Cele două state s-au acuzat la acea vreme reciproc într-o serie de incidente legate de aceeaşi bază rusească, având reţineri în a-şi asuma vreo vină.
Relaţiile lor au mai fost otrăvite şi de disputele din jurul furnizării de gaz rusesc către Ucraina şi de tranzitul aceleiaşi resurse energetice spre Uniunea Europeană.