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