Тем временем война становилась все более жестокой. Тевтонские рыцари казнили всех поляков, захваченных в плен в литовских крепостях, обвиняя их в отступничестве и пособничестве язычникам. Набеги крестоносцев на Самогитию теперь встречали столь слабое сопротивление, что их, скорее, можно было называть охотой на людей. В ответ самогиты время от времени приносили человеческие жертвы своим богам. Они заживо сжигали плененных рыцарей в полном вооружении вместе с конями или расстреливали рыцарей из луков, привязав к священным деревьям. Тем не менее военные действия не были непрерывными. Несмотря на взаимную ожесточенность, заключались перемирия, происходили внезапные смены союзников. И уж совершенно ничто не могло истребить любовь к охоте участников войны с обеих сторон, для чего заключались специальные перемирия.
Хотя Витаутас и был союзником крестоносцев, но видя, как те разоряют его наследные земли, он начал искать другие способы вернуться к власти в Вильнюсе. Умом он осознавал, что лучшим способом для этого было бы объединиться с Ягайло, но Витаутас был человеком страстей, не всегда следовавшим своему рассудку. Кроме того, он не забыл о предательствах Ягайло в прошлом и, хорошо зная о заговорах против себя, окружил себя татарскими телохранителями. Витаутас в своих поступках напоминал маятник, качавшийся от одной стороны к другой, вынужденный искать помощи то у тех, то у других, но никто из доступных ему союзников не был ему по душе. Тевтонские рыцари цинично и философски относились к этому. Как писал один из летописцев:
«Язычники редко поступают так, как должно, и нарушения договоров Витаутасом и его родичами – доказательство тому».
Тем не менее, трезво оценивая свой союз с орденом, Витаутас не мог не приходить к выводу, что эта политика ведет к проигрышу. Победив при таких обстоятельствах, он стал бы обнищавшим правителем, ненавидимым своими подданными и полностью зависимым от воли Великого магистра. Вероятно, он сумел как-то передать Ягайло письмо, усыпив бдительность своего окружения из людей ордена. Если так, письмо наверняка было очень туманным, чтобы не причинить ему вреда, если оно попадет в руки рыцарей. Или, возможно, Ягайло сам ощутил, что настал подходящий момент обратиться к своему двоюродному брату с предложением. Мы знаем точно лишь, что в начале августа 1392 года Ягайло отправил в Пруссию епископа Хенрика Плоцкого в качестве своего эмиссара. Этот мало похожий на священника князь-епископ из династии Пястов был связан браком с сестрой короля – Александрой Мазовецкой. Хенрик использовал возможность, выпавшую при исповеди, чтобы сообщить Витаутасу о предложениях своего хозяина. Витаутас под предлогом того, что его жена хочет повидать родных, отправил Анну, чтобы та провела переговоры с Ягайло. Ему также удалось скрытно освободить многих заложников, которые содержались как почетные пленники в различных крепостях. Затем он передал свою сводную сестру епископу Хенрику и распустил английских крестоносцев, только что прибывших, чтобы принять участие в новом вторжении в Литву. Тем самым он «вывел из игры» лучших лучников Европы, которые не раз показывали свою эффективность в сражениях с подданными Ягайло.
Витаутас тщательно планировал свое предательство. Он разместил в замках крестоносцев самогитских воинов, преданных лично ему, чтобы внезапно перебить или захватить немецкие гарнизоны. После того как ему удалось успешно осуществить этот план, он отправил литовские войска в далеко отстоявшие друг от друга владения ордена в Пруссии и Ливонии и одолел отряды рыцарей, которые размещались в Самогитии. Возвращение Витаутаса в Литву было встречено с бурным восторгом. Все самогиты восхваляли его отвагу и хитрость, сравнивая его гениальную личность с мстительными братьями Ягайло (не в пользу последних), и надеялись, что наконец-то закончилась полоса поражений. Жители же холмистой области Литвы радовались тому, что теперь владычеству иноземцев-поляков приходит конец.
Лишь через год Валленроде смог нанести ответный удар. В январе 1393 года он напал на Гродно с датскими и французскими рыцарями, угрожая перерезать важные коммуникации между Мазовией и Вильнюсом и блокируя Литву. Витаутас и Ягайло обратились к папскому легату, чтобы тот организовал мирные переговоры, которые и состоялись в Торне летом. Через десять дней, однако, Валленроде заболел и покинул Торн, а вскоре скончался.
Новый Великий магистр Конрад фон Юнгинген был решительным лидером с далеко идущими планами. Мира в этом регионе, считал он, можно достигнуть, если одержать решительную победу под Вильнюсом, который и Ягайло, и Витаутасу пришлось бы защищать изо всех сил.