Aux termes d'un traité russo-ukrainien, la flotte est autorisée à séjourner sur le territoire de l'Ukraine (en Crimée) jusqu'en 2017. Le 20 mai dernier, le président ukrainien a chargé le cabinet des ministres de préparer un projet de loi mettant fin à l'accord sur la présence de la flotte en 2017.
Le 30 mai dernier, le commandant en chef de la Marine de guerre russe, Vladimir Vyssotski, a annoncé que la Russie pouvait augmenter le nombre des navires de la flotte à Sébastopol. Selon lui, l'accord de base permet à la Russie de disposer d'une centaine de bâtiments (actuellement, la Flotte compte 35 navires, ses effectifs représentent 11.000 hommes). Ces affirmations sont pourtant contestées par Kiev.
"Si la Russie continue ses jeux politiques et ne retire pas en temps opportun ses navires de Sébastopol, l'Ukraine pourrait les confisquer à titre légal", a annoncé le vice-amiral ukrainien, cité par le service de presse du Parti ukrainien du peuple, dont il est membre. Ce parti est un des neuf fondateurs du bloc électoral et parlementaire Notre Ukraine dirigé par le président Viktor Iouchtchenko.
Moscou estime de son côté que le débat sur les délais du séjour de la flotte est prématurée et que cette question devra faire plus tard l'objet d'un accord spécial avec l'Ukraine.