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