Оценив этот шаг доброй воли, король Ян Казимир осенью 1665 года отправил в Москву своего агента Иеронима Комара и предложил возобновить переговоры в январе следующего года. В октябре царь приказал Ордину-Нащокину возглавить русское посольство на переговорах, дав ему в помощники его родственника Богдана Нащокина и дьяка Григория Богданова. Передав воеводство в Пскове князю И. А. Хованскому, дипломат выехал в Москву для подготовки посольских наказов. Он выступил против проекта наказа, подготовленного сторонниками Никиты Одоевского, где выдвигалось требование передачи Руси всей Малороссии до самого Буга, указывая, что это делает переговоры бессмысленными. Вместо этого он предложил свою давнюю идею — «вечный мир» на условиях разделения украинских земель по Днепру и союза Руси с Речью Посполитой. Для разрешения своего спора с оппонентами он предложил созвать Земский собор. Но правительство отказалось от этой идеи в условиях острого внутреннего кризиса, вызванного церковной реформой и ^прекращающимися народными волнениями. Царь согласился с доводами Ордина-Нащокина и своей рукой вычеркнул из наказа статью о границе по Бугу.
В начале февраля 1666 года Ордин-Нащокин выехал из Москвы в Смоленск. Там он наладил переписку с главой польской делегации, белорусским шляхтичем Юрием Глебовичем, убеждая его поскорее начать переговоры. Их местом была выбрана деревня Андрусово на границе Смоленского и Витебского уездов (сейчас она находится на границе России и Белоруссии). Переговоры открылись только в апреле, когда до места добралась вся польская делегация, и продолжались долгие девять месяцев. Понимая, что сразу разрушить накопившиеся за долгие годы недоверие и взаимные претензии будет сложно, Афанасий Лаврентьевич прибег к тактике поэтапного решения вопросов. Еще до начала переговоров ему удалось добиться договоренности об обмене пленными. 20 мая под предлогом безопасности послов было подписано новое соглашение о повсеместном и бессрочном прекращении боевых действий: стороны обязались вести переговоры до достижения мира или хотя бы перемирия. Еще одно соглашение запрещало полякам заключать союз с татарами — то есть косвенно следовало линии Ордина-Нащокина на союз Польши и России против турецко-татарского союза.
Разрыв связей Речи Посполитой с Крымом ускорился активными попытками татар и стоявших за ними турок подчинить себе Правобережную Украину. В феврале 1666 года гетман Правобережья Дорошенко предложил казакам отказаться от подчинения королю и перейти в подданство крымскому хану. Старшины отвергли это предложение, однако Дорошенко отправил в Бахчисарай письмо с просьбой защитить его от поляков. В сентябре татарское войско под командованием царевича Девлет-Гирея обрушилось на украинские города, уведя оттуда множество пленных. В конце года татары в союзе с казаками Дорошенко разбили под Межибожьем польских полковников Маховского и Красовского, после чего разграбили окрестности Львова и Каменца, где «побрали в плен шляхты, жен и детей, подданных их и жидов до 100 000», Отрезав себе пути к отступлению, Дорошенко стал искать пути к примирению с Москвой и уговаривал пойти на этот шаг крымского хана.
Мятеж правобережного гетмана не сделал поляков более уступчивыми: на начавшихся 20 апреля в Андрусове переговорах они снова потребовали восстановить довоенные границы, отпустить всех пленных и уплатить 10 миллионов злотых контрибуции. Русским оставалось только повторить свои условия: возвратить Белоруссию и выплатить полякам компенсацию за ущерб в размере трех миллионов злотых. Вдобавок поляки в нарушение перемирия попытались взять Витебск, но попытка не удалась, и польские делегаты были вынуждены осудить ее организатора, полковника Чернецкого. Впрочем, русская армия тоже нарушала перемирие: воевода Иван Волконский вместе с левобережным гетманом Брюховецким попытались (и тоже неудачно) отбить у поляков Пропойск и Гомель. В интересах успеха переговоров Ордин-Нащокин потребовал от воеводы прекратить военные действия, что сразу же было представлено его противниками в Москве как непростительная уступка.
Но интриги против дипломата снова не дали результата. 12 июля в Андрусово прибыл царский гонец с приказом отвести войска и всеми силами добиваться мира с поляками. На очередной встрече делегаций Ордин-Нащокин огласил царскую волю: согласиться на возвращение Витебска и Полоцка, но не Смоленска. Поляков это не устроило, и переговоры прервались до сентября. За это время королевское правительство сумело подавить мятеж Любомирского, что побудило поляков занять на переговорах еще более жесткую позицию. Делегаты во главе с Юрием Глебовичем продолжали требовать возвращения всех занятых русскими территорий, включая Смоленск. На это Ордин-Нащокин ответил решительным отказом и угрожал, что русская делегация покинет Андрусово и отправится в Псков на переговоры со шведами. Эта новость встревожила поляков, но, увидев, что русские остаются на месте, они вернулись к прежней политике. 10 декабря по настоянию главы русской делегации было устроено тайное совещание, где полякам намекнули на возможность перехода гетмана Дорошенко в русское подданство. Однако они упрямо требовали возвращения Киева, Динабурга и всех белорусских и украинских земель.