Хотя Витаутас и был союзником крестоносцев, но видя, как те разоряют его наследные земли, он начал искать другие способы вернуться к власти в Вильнюсе. Умом он осознавал, что лучшим способом для этого было бы объединиться с Ягайло, но Витаутас был человеком страстей, не всегда следовавшим своему рассудку. Кроме того, он не забыл о предательствах Ягайло в прошлом и, хорошо зная о заговорах против себя, окружил себя татарскими телохранителями. Витаутас в своих поступках напоминал маятник, качавшийся от одной стороны к другой, вынужденный искать помощи то у тех, то у других, но никто из доступных ему союзников не был ему по душе. Тевтонские рыцари цинично и философски относились к этому. Как писал один из летописцев:

Тем не менее, трезво оценивая свой союз с орденом, Витаутас не мог не приходить к выводу, что эта политика ведет к проигрышу. Победив при таких обстоятельствах, он стал бы обнищавшим правителем, ненавидимым своими подданными и полностью зависимым от воли Великого магистра. Вероятно, он сумел как-то передать Ягайло письмо, усыпив бдительность своего окружения из людей ордена. Если так, письмо наверняка было очень туманным, чтобы не причинить ему вреда, если оно попадет в руки рыцарей. Или, возможно, Ягайло сам ощутил, что настал подходящий момент обратиться к своему двоюродному брату с предложением. Мы знаем точно лишь, что в начале августа 1392 года Ягайло отправил в Пруссию епископа Хенрика Плоцкого в качестве своего эмиссара. Этот мало похожий на священника князь-епископ из династии Пястов был связан браком с сестрой короля – Александрой Мазовецкой. Хенрик использовал возможность, выпавшую при исповеди, чтобы сообщить Витаутасу о предложениях своего хозяина. Витаутас под предлогом того, что его жена хочет повидать родных, отправил Анну, чтобы та провела переговоры с Ягайло. Ему также удалось скрытно освободить многих заложников, которые содержались как почетные пленники в различных крепостях. Затем он передал свою сводную сестру епископу Хенрику и распустил английских крестоносцев, только что прибывших, чтобы принять участие в новом вторжении в Литву. Тем самым он «вывел из игры» лучших лучников Европы, которые не раз показывали свою эффективность в сражениях с подданными Ягайло.

Витаутас тщательно планировал свое предательство. Он разместил в замках крестоносцев самогитских воинов, преданных лично ему, чтобы внезапно перебить или захватить немецкие гарнизоны. После того как ему удалось успешно осуществить этот план, он отправил литовские войска в далеко отстоявшие друг от друга владения ордена в Пруссии и Ливонии и одолел отряды рыцарей, которые размещались в Самогитии. Возвращение Витаутаса в Литву было встречено с бурным восторгом. Все самогиты восхваляли его отвагу и хитрость, сравнивая его гениальную личность с мстительными братьями Ягайло (не в пользу последних), и надеялись, что наконец-то закончилась полоса поражений. Жители же холмистой области Литвы радовались тому, что теперь владычеству иноземцев-поляков приходит конец.

Лишь через год Валленроде смог нанести ответный удар. В январе 1393 года он напал на Гродно с датскими и французскими рыцарями, угрожая перерезать важные коммуникации между Мазовией и Вильнюсом и блокируя Литву. Витаутас и Ягайло обратились к папскому легату, чтобы тот организовал мирные переговоры, которые и состоялись в Торне летом. Через десять дней, однако, Валленроде заболел и покинул Торн, а вскоре скончался.

Новый Великий магистр Конрад фон Юнгинген был решительным лидером с далеко идущими планами. Мира в этом регионе, считал он, можно достигнуть, если одержать решительную победу под Вильнюсом, который и Ягайло, и Витаутасу пришлось бы защищать изо всех сил.

Тем временем в конце 1393 года в Пруссии уже собиралась большая армия французских и немецких крестоносцев, в числе которых был отряд стрелков из Бургундии (возможно, это были английские наемники), способных выкосить ряды язычников столь же успешно, как они делали это на полях сражений Столетней войны. Крестоносцы начали свое движение вверх по Неману в январе 1394 года, полагаясь на толстый лед, служивший им дорогой вглубь Литвы. Витаутас попытался остановить продвижение крестоносцев, но едва избежал гибели под обстрелом, а его поредевшие войска обратились в поспешное отступление перед четырьмя сотнями рыцарей и тысячами сержантов и пехотинцев.

Витаутас получил вскоре подкрепление из Польши – сильный отряд рыцарей, который присоединился к пятнадцати тысячам всадников, уже собравшихся под его началом. Но этого было недостаточно, чтобы остановить наступление крестоносцев. Те прошли через леса, болота и поля, избежав засад, и достигли Вильнюса, где Витаутас объединился с отрядами из русских земель Литвы. Великий князь ввязался в ожесточенное сражение, в котором обе стороны несли большие потери, пока русские полки не побежали, а за ними и литовцы. В конце концов, Витаутасу самому пришлось спасаться бегством, и вновь он едва уцелел. Пока он собирал свои рассеянные и деморализованные войска на безопасном расстоянии, крестоносцы приступили к осаде Вильнюса, города, хорошо знакомого им с 1390 года. Они уже строили планы торжественного крещения литовцев, в этот раз подлинного. Это не должно было походить на ложные обещания честолюбивых Витаутаса и Ягайло, которые вспоминали о своих христианских именах, только подписывая официальные документы. Какие еще требуются доказательства, спрашивали себя крестоносцы, что верность литовских князей Риму слишком ненадежна?

На восьмой день осады под стены прибыл магистр Ливонии со своим войском. Его с радостью встретили. Теперь крестоносцы могли полностью окружить город, блокируя вылазки осажденных, и штурмовать стены в уязвимых местах. Ливонские рыцари были отправлены к берегу, где построили два моста, чтобы, перейдя реку, разорять окрестности столицы. В ходе этого они потеряли пятьдесят человек (в том числе всего трех немцев и только одного рыцаря, что говорит о том, что в войске Ливонского ордена было много местных воинов), перебив и пленив «неисчислимое» количество литовцев. Тем не менее осада шла не слишком успешно. После еще одной недели боев бастионы, которые инженеры выстроили для стрелков, осадные башни и мосты были сожжены во время вылазки гарнизона. Крестоносцы, впрочем, также достигли некоторых успехов. Их артиллерия обрушила каменную башню и подожгла многие деревянные укрепления. Вскоре, однако, уже литовцы подожгли башню в лагере крестоносцев, что не только привело к многочисленным потерям среди французских войск, занимавших ее, но и потере хранившихся в ней припасов. Крестоносцы не могли теперь оставаться под Вильнюсом столько, сколько планировали. Великий магистр позволил войне инженеров продлиться еще четыре дня, но становилось ясно, что литовцы способны уничтожать осадные орудия осаждающих почти с той же скоростью, как те строили их. Для подготовки приступа требовалось больше времени, чем было в распоряжении армии, учитывая нехватку припасов. Кроме того, Витаутас заканчивал перегруппировку своих сил. Разведчики докладывали, что вскоре он может появиться под стенами города, и крестоносцам придется сражаться на два фронта.

Встретившись и обсудив сложившуюся ситуацию, вожди крестоносцев решили сиять осаду. Первыми Великий магистр отправил домой ливонские войска, а затем повел на запад основные силы, преодолевая сопротивления литовцев, которые валили деревья на дорогах и устраивали засады в лесах и на бродах. Прусская часть армии то с помощью переговоров, то силой смогла отступить от Вильнюса, затем резко изменила направление движения и прошла через Самогитию, избежав встречи с усилившейся армией Витаутаса.