Для России наиболее острой проблемой формирования европейской безопасности был вопрос о роли НАТО в новых условиях. Первоначально были распространены представления о том, что НАТО ожидает такая же судьба, как и Организацию Варшавского договора, поскольку исчез главный объект противостояния альянса. Рассчитывали также и на то, что постепенно НАТО будет трансформироваться из преимущественно военной в преимущественно политическую структуру обеспечения безопасности. В декабре 1991 г. Ельцин заявил о готовности России присоединиться к НАТО. Однако развитие событий пошло по третьему сценарию. Произошла переориентация НАТО на новые военно-стратегические цели, был взят курс на расширение круга его участников, появились притязания на исключительное право принимать решения по самым острым вопросам обеспечения европейской безопасности, в том числе и в обход ООН. Россия стремилась противодействовать этим тенденциям, но не сразу.
Во второй половине 1993 г. в связи с обсуждением вопроса о расширении альянса путем включения в него новых членов из числа стран Центральной и Восточной Европы в России началась антинатовская кампания, впервые объединившая самые различные политические силы. Лидеры западных стран были проинформированы о решительном возражении России против включения государств Центральной и Восточной Европы в НАТО. Кампания усилила настроения в пользу присоединения к альянсу у бывших советских союзников, однако оказала определенное влияние и на западные страны. При обсуждении вопроса о расширении стали подчеркивать, что оно не должно привести к возникновению новых разграничительных линий в Европе или оттеснению России. В связи с этим предполагалось параллельное решение двух задач: включение в НАТО новых членов и развитие отношений с Россией.
Для сотрудничества с не участвующими в альянсе странами НАТО в январе 1994 г. была принята программа «Партнерство во имя мира». Москва сдержанно отнеслась к этому проекту, присоединилась к нему лишь в мае 1995 г., но участвовала формально. Российское руководство стремилось обеспечить своей стране особый, более привилегированный статус, но добиться этого не удалось. Ситуация серьезно осложнилась после декабря 1996 г., когда сессия НАТО санкционировала начало процесса расширения альянса. Россия была поставлена перед дилеммой: либо дальнейшее активное противостояние альянсу (со всеми вытекающими из него политическими и военными последствиями), либо, согласившись с решением альянса, попытаться обеспечить прорыв в двусторонних отношениях Россия — НАТО.
Под влиянием российского МИДа и возглавлявшего его Е. М. Примакова выбор был сделан в пользу второго, более прагматичного варианта. В результате в мае 1997 г. стороны подписали Основополагающий акт о взаимных отношениях, сотрудничестве и безопасности. В документе определялись «цели и механизм консультаций и сотрудничества, совместного принятия решений и совместных действий, которые составят ядро взаимоотношений между Россией и НАТО». Был создан Совместный постоянный совет Россия-НАТО. Таким образом закладывались политико-правовые основы для превращения отношений Россия — НАТО в один из центральных элементов европейской безопасности.
Однако дальнейшие события показали, что стороны по-разному трактовали смысл достигнутых договоренностей. Если Россия склонялась к тому, чтобы созданный механизм принимал совместные решения по вопросам безопасности в Европе, то в НАТО его рассматривали лишь как форум для совместного обсуждения проблем, рекомендации которого не носили обязательного характера для руководства альянса. Эти различия в позициях ярко проявились в связи с событиями вокруг Косово в 1999 г.
Для России особенно болезненным было то, что был совершен не просто акт агрессии против ее исторического союзника, а это было сделано вопреки ее активным возражениям. Бомбардировки Югославии показали неготовность лидеров ведущих западных стран превратить отношения Россия — НАТО в значимый компонент европейской безопасности. Более того, альянс претендовал на право применения силы за пределами стран-участниц без санкции Совета Безопасности ООН. В новой «Стратегической концепции НАТО», одобренной на юбилейном саммите альянса в апреле 1999 г., в число задач организации впервые включалось «проведение операций по реагированию на кризисные ситуации», не связанные с коллективной обороной от внешней агрессии.