В течение 1665 года военные действия между Россией и Речью Посполитой почти прекратились, но переговоры о перемирии не шли на лад. Каждая из сторон стояла на своем, и территориальный спор никак не мог найти разрешения. Король Ян Казимир пытался добиться соблюдения условий, на которые Алексей Михайлович пойти не мог (отказ от всех завоеваний России на Украине, в западнорусских землях и в Белоруссии). Показавший себя в качестве умелого дипломата А.Л. Ордин-Нащокин, в то время уже думный дворянин, усиленно уговаривал царя пойти на уступки Речи Посполитой и поскорее заключить с ней мирное соглашение. В одном из писем Алексею Михайловичу он развернул доводы в пользу своей позиции. Не скрывая антишведских настроений, он ссылался на возможности в дальнейшем усилить связи с дунайскими княжествами, которые после заключения договора с Яном Казимиром «пристанут к союзным государствам и отлучатся от турка». Одновременно Ордин-Нащокин давал знать государю, что в Швеции продолжаются антимосковские козни. Они выражались и в том, что там «составляют злые вести, в Стокгольме печатают и во весь свет рассылают, унижая Московское государство». Оскорбительное содержание шведских известий усматривалось в том, что расписывалась слабость России, недостаток у нее войск, значительная часть которых занята подавлением восстаний внутри государства, включая движение в Башкирии. Ордин-Нащокин подозревал в этом шведского резидента в Москве. Под воздействием такого рода известий польская сторона занимает жесткую позицию. Ордин-Нащокин был склонен пожертвовать Украиной, считая казачество опасной для России силой, лишь бы договориться с Яном Казимиром. Отвечая Ордину-Нащокину, Алексей Михайлович со многим согласился, но относительно судьбы Украины был непримирим. Он наставлял своего дипломата, чтобы тот старался на переговорах отстаивать права России на обе стороны Днепра, однако не исключал и некоторого компромисса: «Иди с миром царским путем средним… не уклоняйся ни на десную, ни на шую, Господь с тобой». Последующая секретная инструкция послам предельной чертой уступок предусматривала Днепр, но лишь после конечной неудачи исходного тезиса о полном присоединении Украины. Царь болезненно воспринимал возможные отступления России по территориальному вопросу, считая себя ответственным перед Богом за православное население этого края. Кроме того, присутствовал и исторический довод — принадлежность Руси земель Малороссии и Белоруссии с давних времен. Алексей Михайлович пытался примирить сановных послов Н.И. Одоевского, Ю.А. Долгорукого и других с вчерашним рядовым дворянином Ординым-Нащокиным. Несогласия в посольской команде мешали совершению дела, Ордин-Нащокин откровенно жаловался на именитых собратьев, с горечью замечая: «…они службишке нашей мало доверяют… у нас любят дело и ненавидят, смотря не по делу, а по человеку…» В другом случае он писал Алексею Михайловичу: «За твое государево дело, не страшась никого, я со многими остудился, и за то на меня на Москве от твоих думных людей доклады с посяганьем и из городов отписки со многими неправдами…» Царь по мере сил старался поддержать Ордина-Нащокина, когда тот вступал в пререкания с «породными" сановниками. На жалобу боярина И.А. Хованского Алексей Михайлович отозвался письмом, где были слова; „Афанасий хотя отечеством и меньше тебя, однако великому государю служит верно, от всего сердца“. Напомнив, что князя называли дураком, царь предупреждал, чтобы тот не заносился. Справедливости ради надо сказать, что и сам жалобщик проявлял гордыню и давал немало поводов для недовольства.
Усилия русских дипломатов трудно было подкрепить решительными военными успехами. Но в пользу русской стороны служил слух о том, что Алексей Михайлович якобы собирает войско и сам возглавит новый поход, повторив удачливые действия 1654-1655 годов. Но и в Речи Посполитой внутриполитическое положение было далеко не блестящим. Возникший между королем и магнатом Ю. Любомирским острый конфликт привел к военному столкновению монарха с непокорным вельможей. Ян Казимир дважды потерпел поражение и пошел на переговоры с Любомирским. Продолжать войну с Россией королю было не под силу. Это несколько ускорило продвижение к перемирию. В Москве знали о «рокоте».
На Смоленщине в деревне Андрусово с апреля 1666 года начался новый тур переговоров представителей Речи Посполитой и России. Много времени отнимали споры о причинах нарушения Поляновского мира. Одна сторона обвиняла другую, изощряясь в приведении обоснований. Но главным яблоком раздора являлся вопрос территориальный. Алексей Михайлович произвел перестановки в посольстве, сделав так, что его возглавил Ордин-Нащокин, которого пожаловали чином окольничего. Этому дипломату царь доверял больше других и надеялся на благоприятный исход переговоров. Между Москвой и Андрусовом сновали гонцы с инструкциями от царя и отписками Ордина-Нащокина. Алексей Михайлович внимательно следил за развитием событий. Состоялось уже тридцать посольских съездов, а согласованного результата все не было. Царь подбадривал Ордина-Нащокина не только грамотами. Его любимец получал от него изысканные яства и заграничные вина — романею, рейнское, кагор и др.
Пока шли словесные баталии в Андрусове, на юге Украины произошли серьезные перемены. Провозглашенный гетманом Правобережья П.Д. Дорошенко выступил одновременно против Варшавы и Москвы. Крымская орда, ранее поддерживавшая Яна Казимира, теперь взяла сторону Дорошенко. Казацко-татарское войско разгромило поляков. Татарские загоны рассыпались на больших территориях Украины и пограничных польских областей. В плен были уведены десятки тысяч людей. В этой ситуации Дорошенко предпринимал усилия для сохранения состояния войны России с Яном Казимиром. Обстановка позволила московским дипломатам укрепить свою позицию на переговорах. Польские комиссары долго не хотели и слышать, чтобы Киев достался России на каких-либо условиях. В тайных «статьях» А. Л. Ордину-Нащокину царь уже был готов совсем отказаться от Киева, имея согласие другой стороны на передачу России Левобережья Украины. Однако успехи Дорошенко побудили царя еще раз попытаться «разыграть» киевскую карту. Киев временно должен был находиться в руках русских, затем предстояла его передача Речи Посполитой. При этом в ход были пущены закулисные денежные выдачи комиссарам Речи Посполитой, от которых те не отказались.
В итоге 31 января 1667 года было достигнуто общее соглашение о перемирии на тринадцать с половиной лет. К России отходили Смоленская земля, Северщина, Левобережная Украина и на два года — Киев с окрестностями. Запорожской Сечи договор предусматривал двойное подчинение. Обусловлен был обмен пленными. Только о «пашенных людях» предстояло согласовать вопрос на последующих переговорах. В случае враждебных действий Крыма против обеих частей Украины царь и король выступают на защиту совместно. Объявлялись свободными торговые отношения между подданными обоих государств. Прибывшие затем в Москву посланцы Речи Посполитой, подтверждая договор, заявили, что нужно дать компенсацию шляхте, изгнанной из Левобережья и Северской земли («потому что от нее беспрестанная докука и вопль»). Для удовольствия этих «выгнанцев» посланцы запросили огромную сумму, с которой русская сторона решительно не согласилась. И все же царь позволил выдать из казны один миллион польских злотых (по другим данным — две тысячи рублей).
Прием в Москве польских послов был чрезвычайно радушным. Тогда им «явили» наследника престола царевича Алексея Алексеевича, намекнув, что они видят возможного короля Речи Посполитой, поскольку этот вопрос время от времени всплывал в ходе переговоров. Как известно, Ян Казимир был бездетен, а потому введение наследственной монархии в данном случае исключалось.
Заключение Андрусовского перемирия стало важнейшим внешнеполитическим событием. Оно положило конец вековому противостоянию Речи Посполитой и России, будучи в 1686 году подтверждено Вечным миром. Киев так и остался в пределах России. Было закреплено воссоединение Левобережной Украины с Россией, возвращены старинные западно-русские земли.
Решая одни проблемы, Россия волей-неволей вовлекалась в водоворот других. А они сгущались на юге, где нависала угроза борьбы с Крымским ханством и Османской империей. Впрочем, эта забота была и у речи Посполитой, что послужило главным предметом обсуждений на встречах представителей примирившихся государств. Ближайшие годы показали обоснованность таких опасений.
Правительство Алексея Михайловича понимало значение акта, заключенного в Андрусове, и приложило много усилий, чтобы его результаты стали международным достоянием. Русские посольства посещают ряд европейских стран. Это было сопряжено также с признанием за царем нового титула. В основном поставленная цель была достигнута. Окончание войны торжественно отметили в Москве. Царь пожаловал служилых людей двадцатипроцентной передачей из поместных земель в вотчины. Наибольших царских милостей удостоился А.Л. Ордин-Нащокин. Он стал боярином, получил необычное титулование «царственной большой печати и государственных великих посольских дел сберегатель» и был назначен начальником Малороссийского и Польского приказов.
