Тем временем боевые действия со шведами продолжались. Помимо рижского направления война велась на юго-востоке Ливонии, где в 1656 году был взят Юрьев (Тарту), и в Ингерманландии, где русские под командованием Потемкина осадили сильную крепость Нотебург (Орешек). Тем временем шведы возобновили военные действия в Польше. Летом король Карл X заключил союз с Бранденбургом и Трансильванским герцогством, а также с Богданом Хмельницким, пригласив их поучаствовать в разделе Польши. Это позволило шведской армии, вторгнувшись в польские пределы, захватить Варшаву, что заставило больного и уставшего короля Яна Казимира покинуть страну. Однако сплотившиеся против шведов польские магнаты укрепились на юге и отбили наступление казаков и трансильванцев. Полякам удалось вовлечь в военные действия на своей стороне Бранденбург и Данию, заручившись поддержкой Священной Римской империи — давнего противника протестантской Швеции. Когда летом 1657 года датский флот напал на шведские порты, большая часть армии Карла X была вынуждена покинуть Польшу.
Несмотря на то что значительные силы шведов были заняты на польском направлении, у них хватало сил вести наступление в Ливонии. Угроза возобновления войны с поляками заставила Боярскую думу принять в феврале 1657 года решение «промышлять всякими мерами, чтобы привести шведов к миру». Однако шведский главнокомандующий Магнус Делагарди, отвергнув предложения о мире, вторгся в русские земли и взял штурмом Псково-Печерский монастырь. Его дальнейшее продвижение остановил в битве у деревне Мигузице князь Матвей Шереметев, чьи люди «графа Магнуса и его полку неметцких людей многих побили и языки поймали». Однако в июне Делагарди разбил отряд Шереметева под Валком, взяв в плен самого князя. После этого он попытался захватить Юрьев, но был отбит. Неудачей закончилась и попытка шведов взять соседний город Гдов. У стен города Делагарди был разбит князем Иваном Хованским, что вызвало у русских ликование. В занятых ими городах, включая Царевич-Дмитриев, где был воеводой Ордин-Нащокин, был устроен пушечный салют.
После этого войска Хованского, переправившись через реку Нарва, вторглись в Ингерманландию. Не дойдя до Ревеля, они были вынуждены остановиться из-за новых слухов об эпидемии чумы. В начале 1658 года русские возобновили наступление, но шведы, пользуясь выходом из войны повергнутой ими Дании, перебросили в Ливонию значительные силы. Губернатор Нарвы Густав Горн не только отбил новое наступление Хованского, но и вернул Ниеншанц и его окрестности. На этом военные действия прекратились; обе стороны истощили свои силы и искали возможности примирения, тем более что обстановка на Украине становилась все более тревожной. В августе Горн и Хованский согласились на переговоры, начавшиеся в октябре в местечке Валиесари под Нарвой. Главным переговорщиком с русской стороны выступал Ордин-Нащокин, которому еще в апреле царем были переданы соответствующие полномочия вместе со званием думного дворянина.
Формально главой посольства в переговорах со шведами был назначен боярин П. С. Прозоровский, но Алексей Михайлович в тайном письме Нащокину предписывал ему вести все важные переговоры и в случае надобности подкупить шведских послов «соболями и ефимками». Царь во что бы то ни стало желал сохранить за Россией гавани на Неве (Орешек) и Западной Двине (Кукенойс), но шведы всячески противились этому. Видя в Нащокине стойкого защитника русских интересов, они пытались возражать против его участия в переговорах. Его ведущая роль не нравилась и русским участникам посольства, которые писали царю письма с жалобами на «самоправство» дипломата. К этому добавился скандал, учиненный псковским воеводой Хованским — когда послы захотели взять с собой для защиты часть подчиненных ему войск, он написал кляузу царю. Афанасий Лаврентьевич, в свою очередь, обвинил князя в полководческой бездарности, приведя в пример свои успешные действия в Ливонии: «Вот мне не было прислано указа, чтобы идти под Мариенбург, но я, видя, что наших ратных людей из Полоцка и Пскова нет, а шведы в сборе, призвал к себе Гонсевского и пустил в Лифляндию и затем взял город Мариенбург».
Благодаря дипломатическому искусству Ордина-Нащокина 1 декабря сторонам удалось заключить Валиесарское перемирие сроком на три года, исходя из принципа «utipossidetis» — «каждый владеет тем, чем владеет». Это соглашение сохраняло за русскими все их завоевания в Ливонии. Однако по истечении срока перемирия Швеция начала шантажировать царское правительство, угрожая войной. В апреле 1660 года новый шведский король Карл XI подписал с поляками Оливский мир, что делало возможным совместное выступление двух стран против Руси. В этих условиях Алексей Михайлович потребовал скорейшего мира со шведами, даже на условиях возвращения им занятой русскими части Ливонии. Ордин-Нащокин выступал против подобных планов, советуя лучше помириться с поляками: «Взять Полоцк и Витебск, а если поляки заупрямятся, то и этих городов не надобно; прибыли от них никакой нет, а убытки большие, надобно будет беспрестанно помогать всякою казною да держать в них войско. Другое дело Лифляндская земля: от нея русским городам, Новгороду и Пскову, великая помощь будет хлебом, а из Полоцка и Витебска Двиною будут ходить некоторые товары, а с них будет взиматься большая пошлина в Лифляндских городах. <…> А если с польским королем мир заключен будет обидный, то он не будет крепок, потому что Литва и Польша не за морем, причина к войне скоро найдется»[22].