Проте, не зважаючи на декларовані ідеї співпраці в сфері підтримки стабільності в Європі, російське керівництво зберігало негативне ставлення до планів щодо розширення НАТО на схід. Це досить яскраво проявилося у заяві Б.Єльцина під час Будапештської зустрічі глав держав-учасниць Наради з безпеки і співробітництва в Європі (НБСЄ), що проходила в грудні 1994 року, де було сказано, що "плани розширення НАТО сіють зерна недовіри, створюють нові смуги розмежування і цим самим суперечать налагодженню справжнього партнерства і формування єдиної демократичної Європи" [114, c.231].

У відповідь на активізацію дій Заходу, спрямованих на географічне розширення альянсу, російське керівництво висунуло ідею створення нового військово-політичного блоку на чолі з Росією, який би об'єднував країни СНД. Таким чином відбувався би новий розкол Європи на два полюси протистояння, що призвело б до різкого погіршання міжнародної ситуації в цілому і сприяло б наростанню конфронтації між Сходом і Заходом. Однак, реальних можливостей в Москви для створення такого військово-політичного союзу в найближчому майбутньому не було. Спроба створити противагу НАТО на основі підписаного в 1992 р. в Ташкенті Договору про колективну безпеку виявилась утопією через численні існуючі між країнами-учасницями суперечності [44, c.7].

В пошуках інструментів для протидії вступу країн Центрально-Східної Європи в Північноатлантичний альянс керівництво Росії виявилось безсилим. Найбільш адекватною в цій ситуації стала політика Кремля, спрямована на розтягнення процесу розширення НАТО на Схід на якнайтриваліший відрізок часу. Одночасно активно проводились пошуки взаємоприйнятних форм співпраці [64, c.17].

Однак, "Дослідження з питання про розширення НАТО", проведене альянсом у вересні 1995 р., засвідчило серйозність намірів Заходу щодо прийняття країн Центрально-Східної Європи в свій склад. Стосовно позиції Росії щодо цього процесу, було висловлене запевнення, що "процес розширення НАТО, в тому числі пов'язані з ним військові домовленості, нікому не загрожуватимуть і сприятимуть розвиткові широкої архітектури європейської безпеки, яка ґрунтується на справжній співпраці у межах усієї Європи і зміцнює безпеку і стабільність для усіх" [3, c.404].

В результаті активізації дій, спрямованих на розширення НАТО, відбулася певна перестановка сил у вищому державному керівництві Росії. Восени 1995 р. Є.Прімаков змінив на посаді міністра закордонних справ Російської Федерації А.Козирєва, який був прибічником прозахідного курсу. Такі дії Кремля засвідчили остаточне завершення "романтичного періоду" у взаємовідносинах між Росією і Заходом. Новий міністр закордонних справ, розуміючи неспроможність Москви вплинути на рішення НАТО про розширення, зайняв позицію, спрямовану на досягнення домовленостей, які б компенсували Росії вихід Центрально-Східної Європи із сфери її впливу [52, с.64].

Ці події відбувалися на фоні активізації східноєвропейської політики Північноатлантичного альянсу. Першим важливим кроком на цьому шляху стало рішення Ради НАТО про початок розширення альянсу. 10 грудня 1996 року країни-члени НАТО розпочали роботу з вироблення рекомендацій того, котрій з країн Центрально-Східної Європи слід запропонувати переговори з приводу її вступу в альянс. Це стало своєрідним свідченням початку формування нової структури міждержавних відносин в Європі. Такому заходові передували і після нього були продовжені активні переговори з 12 країнами Центральної, Східної і Південно-Східної Європи, які зацікавились запропонованою перспективою. Одночасно здійснювалась розробка нової стратегічної концепції Північноатлантичного альянсу, обговорювались форми і темпи його розширення [27, с.26]. На початку 1997 р. На прохання країн - партнерів відбувся активний індивідуальний діалог з кожною із них. Паралельно військові органи НАТО провели незалежний та об'єктивний аналіз відповідних військових чинників стосовно тих країн, які зацікавлені у членстві в альянсі [111, с. 81].

Результатом такої діяльності стало офіційне запрошення країнами-членами НАТО під час Мадридського самміту в липні 1997 р. Польщі, Чеської Республіки та Угорщини до участі в переговорах з питань приєднання до альянсу. Аргументом таких дій послужила Стаття 10 Північноатлантичного договору від 4 квітня 1949 р., відповідно до якої країни - члени НАТО "можуть за одностайною згодою запросити приєднатися до цього Договору будь-яку іншу європейську державу, здатну втілювати у життя принципи цього Договору і сприяти безпеці у Північноатлантичному регіоні" [9, с. 541-542]. Також було підтверджено той факт, що НАТО залишається відкритою організацією для нових членів відповідно до вище згаданої статті 10 цього договору [111, с. 81]. 16 грудня 1997 р. міністри закордонних справ країн-членів НАТО підписали в Брюсселі з Польщею, Чехією та Угорщиною протоколи про приєднання цих країн до Північноатлантичного альянсу [103, с.32].

Одночасно альянсом було здійснено ряд заходів, спрямованих на зняття напруженості у відносинах з Росією, що зі свого боку всіляко намагалася з'ясувати реальні можливості досягнення домовленостей, які б могли гарантувати безпеку Росії. При цьому Росія зберігала негативне ставлення до членів щодо розширення НАТО [80, с.22].

Такий курс Кремля частково виправдав себе і керівництво альянсу вирішило розпочати з Росією переговори стосовно тих питань, які найбільше турбували Москву в плані процесу розширення НАТО на Схід. В ході закритих консультацій, які розпочалися в серпні 1996 р. стали визначатись основні риси можливих домовленостей. В грудні 1996 р. на Сесії Ради НАТО на рівні міністрів закордонних справ було зроблено заяву про те, що процес розширення НАТО жодним чином не вплине на ядерну політику