Понимая, как трудно будет добиться примирения с Речью Посполитой, он решал эту проблему постепенно. В марте — апреле произошел обмен пленными, в мае было достигнуто соглашение о безопасности послов. Но в июне обнаружилась полная несовместимость позиций сторон в вопросах о границах, пленных, контрибуции. От русского великого и полномочного посла требовалась большая выдержка, чтобы не прервать переговоров. Период с сентября по ноябрь 1666 года характеризуется сильнейшими дипломатическими атаками поляков, которые стали добиваться возвращения всей Литвы, Белоруссии и Украины. Но руководитель русской делегации твердо заявил, что «царь не пойдет на уступку Украины». Польские комиссры пригрозили продолжением войны. В отчете в Москву Ордин-Нащокин советовал царю принять польские условия. В последних числах декабря от имени царя полякам был уступлен Динабург, но послы настаивали на признании за Россией Киева, Запорожья и всей Левобережной Украины.
К концу года внешнеполитическое положение Речи Посполитой изменилось, и польские представители стали уступчивей. Уже будучи опальним, Ордин-Нащокин вскоре принимает самое деятельное участие в возобновившихся русско-польских переговорах. Его выдержка, хладнокровие дипломатическая мудрость во многом предопределили подписание 30 января (9 февраля) 1667 года важнейшего соглашения — Андрусовского мира, подведшего итог длительной русско-польской войне. Устанавливалось перемирие на 13,5 лет. Были решены и другие важные вопросы двусторонних отношений, в частности предусматривались совместные действия против крымско-османских нападений. По инициативе Ордина-Нащокина во многие страны (Англию, Бранденбург, Голландию, Данию, Империю, Испанию, Персию, Турцию, Францию, Швецию и Крым) были направлены русские дипломаты с «объявительными грамотами» о заключении Андрусовского перемирия, предложением дружбы, сотрудничества и торговли. «Гремеви в Европе слава тридцатилетнего перемирия, которого желали все христианские державы, — писал современник дипломата, — воздвигнет Нащокину благороднейший памятник в сердцах потомков».
Переговоры, подготовлявшие Андрусовский мир, проходили в несколько туров. И возвращение Ордина во время одного из перерывов в Москву (1664) совпало с судом над патриархом Никоном и его сторонником — боярином Н.И. Зюзиным, к которому Ордин относился с сочувствием. Эта бросило тень на думного дворянина, хотя его пособничество Никону доказано не было. Все же Афанасию Лаврентьевичу пришлось просить у царя прощения. Только доверие Алексея Михайловича, а также бескорыстие и честность самого Ордина-Нащокина спасли его от тяжелых последствий: его лишь удалили в Псков воеводой. Но и в этой должности Ордин оставалс дипломатом. Он вел переговоры и переписку с литовскими и польскими магнатами, размышлял о разграничении пограничных со Швецией земель. А для продвижения дела о мире с Речью Посполитой старался привлечь к посредничеству правителей Австрии и Бранденбурга, Дании и Курляндии.
Будучи человеком образованным, Ордин и сыну своему постарался дать хорошее образование. Воин Афанасьевич «был известен как умный, распорядительный молодой человек», даже замещавший иногда отца в Кокнее (Царевичеве-Дмитриеве городе). Но «страсть к чужеземцам, нелюбье к своему» привели его к бегству за границу. Правда, в 1665 году он вернулся из-а границы, и ему разрешили жить в отцовской деревне. Однако служебнй карьере Ордина-Нащокина это не повредило.
В феврале 1667 года Ордин-Нащокин был пожалован званием ближнего боярина и дворецкого и вскоре назначен в Посольский приказ в звании «Царственных и государственных посольских дел боярина». Летом того же года руководитель Посольского приказа разработал и образец новой государственной печати, после утверждения которого получил титул «Царственных большие печати и государственных великих посольских дел сберегателя» Затем ему были вверены смоленский разряд, малороссийский приказ, новгородская, галицкая и владимирская и некоторые другие приказы, в результате чего он сосредоточил в своих руках не только внешнеполитические, но и многие внутригосударственные ведомства, став фактическим главе правительства.
Ордина-Нащокин уделял большое внимание расширению и укреплению международных связей России. Именно он попытался организовать постоянные дипломатические представительства эа рубежом. Так, в июле 1668 года Василий Тяпкин был отправлен в Речь Посполитую «для бытия тамо навсегда резидентом».
Расширение внешних связей требовало определенной осведомленности о событиях за пределами страны. С этой целью по инициативе руководителя приказа была установлена почтовая связь с Вильно и Ригой. Он же ввел практику перевода иностранных газет и вестовых писем, из которых составлялись сводные выписки — «Куранты». Эти рукописные листки стали предшественниками печатных газет.