Проблема расширения НАТО на восток, особенно активно дискутировавшаяся в 1996 году, вызывала большую обеспокоенность в Москве. Эта обеспокоенность усиливалась ввиду явного желания Украины вступить в более тесные отношения с Североатлантическим альянсом, нежели те, которые имели место к этому времени. Весной 1997 года ряд политиков на Западе (в частности, министр иностранных дел М. Рифкинд) заявляли о том, что НАТО необходимо расширить до восточных границ Украины. На известные решения Совета Федерации России Госдепартамент США откликнулся специальным документом, в котором выразил «сожаление» в связи с решением СФ по Севастополю. В Киеве подобные заявления воспринимались с большим интересом, причем президент Украины Л. Кучма и председатель Совета национальной безопасности В. Горбулин не раз говорили о том, что крен украинской политики в сторону Запада обусловлен «агрессивной политикой России».[149]
Весной 1997 года В. Горбулин заявил также о возможности пересмотра в дальнейшем внеблокового статуса Украины и вступления ее в НАТО. Тогда же в Брюсселе начались переговоры по подготовке документа об особом партнерстве Украины и НАТО. Еще раньше была достигнута договоренность о проведении в августе 1997 года в Крыму специальных учений ВМС Украины и стран членов НАТО (Си-Бриз-97). Сценарий этих учений стал еще одним источником трений России и Украины. Как отмечалось в прессе, первоначально должны были отрабатываться военные действия против «сепаратистов», которым оказывает помощь соседняя держава, в чем российские политики и военные усмотрели намек на крымское республиканское движение и российский Черноморский флот. Несмотря на то, что в дальнейшем сценарий был изменен (в регионе происходит землетрясение, после которого начинаются «выступления повстанцев»), Россия наотрез отказалась принимать участие в учениях.Возможный альянс Украины и НАТО вызвал большую озабоченность внешнеполитического ведомства России и заставил активизировать процесс поиска решения по Севастополю и флоту (возможно, это было связано с новой линией МИДа РФ, осуществлявшейся Е. Примаковым). Это проявилось уже в изменении позиции по отношению к Украине. Как отмечал