Оценив этот шаг доброй воли, король Ян Казимир осенью 1665 года отправил в Москву своего агента Иеронима Комара и предложил возобновить переговоры в январе следующего года. В октябре царь приказал Ордину-Нащокину возглавить русское посольство на переговорах, дав ему в помощники его родственника Богдана Нащокина и дьяка Григория Богданова. Передав воеводство в Пскове князю И. А. Хованскому, дипломат выехал в Москву для подготовки посольских наказов. Он выступил против проекта наказа, подготовленного сторонниками Никиты Одоевского, где выдвигалось требование передачи Руси всей Малороссии до самого Буга, указывая, что это делает переговоры бессмысленными. Вместо этого он предложил свою давнюю идею — «вечный мир» на условиях разделения украинских земель по Днепру и союза Руси с Речью Посполитой. Для разрешения своего спора с оппонентами он предложил созвать Земский собор. Но правительство отказалось от этой идеи в условиях острого внутреннего кризиса, вызванного церковной реформой и ^прекращающимися народными волнениями. Царь согласился с доводами Ордина-Нащокина и своей рукой вычеркнул из наказа статью о границе по Бугу.

В начале февраля 1666 года Ордин-Нащокин выехал из Москвы в Смоленск. Там он наладил переписку с главой польской делегации, белорусским шляхтичем Юрием Глебовичем, убеждая его поскорее начать переговоры. Их местом была выбрана деревня Андрусово на границе Смоленского и Витебского уездов (сейчас она находится на границе России и Белоруссии). Переговоры открылись только в апреле, когда до места добралась вся польская делегация, и продолжались долгие девять месяцев. Понимая, что сразу разрушить накопившиеся за долгие годы недоверие и взаимные претензии будет сложно, Афанасий Лаврентьевич прибег к тактике поэтапного решения вопросов. Еще до начала переговоров ему удалось добиться договоренности об обмене пленными. 20 мая под предлогом безопасности послов было подписано новое соглашение о повсеместном и бессрочном прекращении боевых действий: стороны обязались вести переговоры до достижения мира или хотя бы перемирия. Еще одно соглашение запрещало полякам заключать союз с татарами — то есть косвенно следовало линии Ордина-Нащокина на союз Польши и России против турецко-татарского союза.

Разрыв связей Речи Посполитой с Крымом ускорился активными попытками татар и стоявших за ними турок подчинить себе Правобережную Украину. В феврале 1666 года гетман Правобережья Дорошенко предложил казакам отказаться от подчинения королю и перейти в подданство крымскому хану. Старшины отвергли это предложение, однако Дорошенко отправил в Бахчисарай письмо с просьбой защитить его от поляков. В сентябре татарское войско под командованием царевича Девлет-Гирея обрушилось на украинские города, уведя оттуда множество пленных. В конце года татары в союзе с казаками Дорошенко разбили под Межибожьем польских полковников Маховского и Красовского, после чего разграбили окрестности Львова и Каменца, где «побрали в плен шляхты, жен и детей, подданных их и жидов до 100 000», Отрезав себе пути к отступлению, Дорошенко стал искать пути к примирению с Москвой и уговаривал пойти на этот шаг крымского хана.

Мятеж правобережного гетмана не сделал поляков более уступчивыми: на начавшихся 20 апреля в Андрусове переговорах они снова потребовали восстановить довоенные границы, отпустить всех пленных и уплатить 10 миллионов злотых контрибуции. Русским оставалось только повторить свои условия: возвратить Белоруссию и выплатить полякам компенсацию за ущерб в размере трех миллионов злотых. Вдобавок поляки в нарушение перемирия попытались взять Витебск, но попытка не удалась, и польские делегаты были вынуждены осудить ее организатора, полковника Чернецкого. Впрочем, русская армия тоже нарушала перемирие: воевода Иван Волконский вместе с левобережным гетманом Брюховецким попытались (и тоже неудачно) отбить у поляков Пропойск и Гомель. В интересах успеха переговоров Ордин-Нащокин потребовал от воеводы прекратить военные действия, что сразу же было представлено его противниками в Москве как непростительная уступка.

Но интриги против дипломата снова не дали результата. 12 июля в Андрусово прибыл царский гонец с приказом отвести войска и всеми силами добиваться мира с поляками. На очередной встрече делегаций Ордин-Нащокин огласил царскую волю: согласиться на возвращение Витебска и Полоцка, но не Смоленска. Поляков это не устроило, и переговоры прервались до сентября. За это время королевское правительство сумело подавить мятеж Любомирского, что побудило поляков занять на переговорах еще более жесткую позицию. Делегаты во главе с Юрием Глебовичем продолжали требовать возвращения всех занятых русскими территорий, включая Смоленск. На это Ордин-Нащокин ответил решительным отказом и угрожал, что русская делегация покинет Андрусово и отправится в Псков на переговоры со шведами. Эта новость встревожила поляков, но, увидев, что русские остаются на месте, они вернулись к прежней политике. 10 декабря по настоянию главы русской делегации было устроено тайное совещание, где полякам намекнули на возможность перехода гетмана Дорошенко в русское подданство. Однако они упрямо требовали возвращения Киева, Динабурга и всех белорусских и украинских земель.

Ордин-Нащокин оказался в сложном положении: данные ему инструкции не позволяли идти на столь серьезные уступки, а неудача переговоров грозила крахом его карьеры. Вдобавок он знал, что русская армия устала от войны, казна пуста, а на Волге разворачивается крестьянская война под предводительством Степана Разина. Обо всем этом он писал царю, советуя принять условия поляков хотя бы на время, до улучшения положения в стране. Но правительство Алексея Михайловича не дало на это согласия и отозвало в Москву для консультаций дьяка Г. Богданова — не исключено, что враги Нащокина хотели добиться от него «компромата» на думного дворянина. Самому Ордину-Нащокину было приказано временно воздержаться от встреч с польскими комиссарами. Переговоры возобновились в конце декабря, когда Богданов вернулся из Москвы. 28 декабря полякам от царского имени пообещали вернуть Ди-набург, а в ответ на это от них потребовали признания за Россией Киева, Запорожья и всей Левобережной Украины.

Еще до этого, 20 декабря, заседание польского сейма рекомендовало комиссарам немедленно заключить перемирие с Россией, уступив ей на время Киев и даже Динабург. Это объяснялось как наступлением татар и казаков на юге, так и новыми волнениями знати против короля Яна Казимира. Пытаясь спасти то, что еще можно, польские комиссары согласились на предложения русской стороны. 3 января на очередном заседании удалось согласовать будущие границы, а 20 января Андрусове кий договор был торжественно подписан; от русской делегации подпись под ним поставил окольничий Ордин-Нащокин. Согласно договору устанавливалось перемирие на 13 с половиной лет; России были переданы Смоленское и Черниговское воеводства, а также Стародуб и Северская земля. На Украине граница проходила по Днепру, а Киев с округой отдавался Руси на два года до новых переговоров. Запорожье становилось общим владением Руси и Польши «на общую их службу от наступающих басурманских сил». Особые статьи договора определяли порядок возвращения пленных и возврата захваченного во время войны имущества; гарантировались свобода торговли и дипломатическая неприкосновенность послов. Была отмечена готовность сторон вместе противостоять татарским набегам — идея Ордина-Нащокина о союзе двух стран против турецко-татарской угрозы обретала реальность. Однако решение вопроса отложили до ратификации договора в Москве и Варшаве.

1 февраля 1667 года царь и его двор торжественно встретили вернувшееся в Москву посольство в Дорогомиловской слободе. Вместе они проследовали в Кремль, где думный дьяк Дементий Башмаков объявил собравшейся толпе результаты переговоров. На следующий день Ордин-Нащокин был пожалован в бояре, а 25 февраля назначен главой Посольского приказа в звании «царственных и государственных посольских дел оберегателя». Под его управление было передано и еще несколько ведомств: Смоленский разряд, Малороссийский приказ, Новгородская, Галицкая и Владимирская чети, вяземская таможня, кружечный двор, заведование железными заводами. В награду от царя он получил 500 крестьянских дворов в Костромском уезде и Порецкую волость под Смоленском, а также атласную шубу на соболях ценой 200 рублей. Так началась новая глава биографии Ордина-Нащокина, выдвинувшая его на уровень вершителя судеб Русского государства.