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