На межі століть, коли навіть президент Путін, що тоді обіймав посаду прем’єр-міністра, подейкував про вступ Росії до НАТО, у Відні був успішно розпочатий та завершений за участю Росії та України переговорний процес щодо створення Міжнародного воєнно-морського контингенту для підтримки безпеки в Чорноморському регіоні — BLACKSEAFOR. Вказана Чорноморська військово-морська група оперативної взаємодії була створена у 2001 році. До її складу ввійшли, окрім російського, українського та грузинського, флот НАТО в складі військово-морських сил Румунії, Болгарії та Туреччини. Багатофункціональне об’єднання мало виконувати роль «швидкої допомоги» та «поліції» Чорного моря. Основні задачі групи полягали в пошуку та рятуванні кораблів, що зазнали лиха; терміновій доставці гуманітарних вантажів; боротьбі з порушниками екології та знешкодженні вибухонебезпечних предметів; боротьбі з піратством та міжнародним тероризмом. Зручна Севастопольська бухта мала стати місцем базування такого міжнародного військово-морського підрозділу, що мав слугувати справі миру, а не війни. Непогана орендна плата від сусідніх країн та НАТО могла перетворити Кримський півострів в зону міжнародного туризму та розважального бізнесу.