Тем временем в конце 1393 года в Пруссии уже собиралась большая армия французских и немецких крестоносцев, в числе которых был отряд стрелков из Бургундии (возможно, это были английские наемники), способных выкосить ряды язычников столь же успешно, как они делали это на полях сражений Столетней войны. Крестоносцы начали свое движение вверх по Неману в январе 1394 года, полагаясь на толстый лед, служивший им дорогой вглубь Литвы. Витаутас попытался остановить продвижение крестоносцев, но едва избежал гибели под обстрелом, а его поредевшие войска обратились в поспешное отступление перед четырьмя сотнями рыцарей и тысячами сержантов и пехотинцев.
Витаутас получил вскоре подкрепление из Польши – сильный отряд рыцарей, который присоединился к пятнадцати тысячам всадников, уже собравшихся под его началом. Но этого было недостаточно, чтобы остановить наступление крестоносцев. Те прошли через леса, болота и поля, избежав засад, и достигли Вильнюса, где Витаутас объединился с отрядами из русских земель Литвы. Великий князь ввязался в ожесточенное сражение, в котором обе стороны несли большие потери, пока русские полки не побежали, а за ними и литовцы. В конце концов, Витаутасу самому пришлось спасаться бегством, и вновь он едва уцелел. Пока он собирал свои рассеянные и деморализованные войска на безопасном расстоянии, крестоносцы приступили к осаде Вильнюса, города, хорошо знакомого им с 1390 года. Они уже строили планы торжественного крещения литовцев, в этот раз подлинного. Это не должно было походить на ложные обещания честолюбивых Витаутаса и Ягайло, которые вспоминали о своих христианских именах, только подписывая официальные документы. Какие еще требуются доказательства, спрашивали себя крестоносцы, что верность литовских князей Риму слишком ненадежна?
На восьмой день осады под стены прибыл магистр Ливонии со своим войском. Его с радостью встретили. Теперь крестоносцы могли полностью окружить город, блокируя вылазки осажденных, и штурмовать стены в уязвимых местах. Ливонские рыцари были отправлены к берегу, где построили два моста, чтобы, перейдя реку, разорять окрестности столицы. В ходе этого они потеряли пятьдесят человек (в том числе всего трех немцев и только одного рыцаря, что говорит о том, что в войске Ливонского ордена было много местных воинов), перебив и пленив «неисчислимое» количество литовцев. Тем не менее осада шла не слишком успешно. После еще одной недели боев бастионы, которые инженеры выстроили для стрелков, осадные башни и мосты были сожжены во время вылазки гарнизона. Крестоносцы, впрочем, также достигли некоторых успехов. Их артиллерия обрушила каменную башню и подожгла многие деревянные укрепления. Вскоре, однако, уже литовцы подожгли башню в лагере крестоносцев, что не только привело к многочисленным потерям среди французских войск, занимавших ее, но и потере хранившихся в ней припасов. Крестоносцы не могли теперь оставаться под Вильнюсом столько, сколько планировали. Великий магистр позволил войне инженеров продлиться еще четыре дня, но становилось ясно, что литовцы способны уничтожать осадные орудия осаждающих почти с той же скоростью, как те строили их. Для подготовки приступа требовалось больше времени, чем было в распоряжении армии, учитывая нехватку припасов. Кроме того, Витаутас заканчивал перегруппировку своих сил. Разведчики докладывали, что вскоре он может появиться под стенами города, и крестоносцам придется сражаться на два фронта.
Встретившись и обсудив сложившуюся ситуацию, вожди крестоносцев решили сиять осаду. Первыми Великий магистр отправил домой ливонские войска, а затем повел на запад основные силы, преодолевая сопротивления литовцев, которые валили деревья на дорогах и устраивали засады в лесах и на бродах. Прусская часть армии то с помощью переговоров, то силой смогла отступить от Вильнюса, затем резко изменила направление движения и прошла через Самогитию, избежав встречи с усилившейся армией Витаутаса.
Этот поход стал одним из самых памятных предприятий в Средние века – осада вражеской столицы рыцарями и военными специалистами со всей Европы. Несмотря на высокий дух крестоносцев, они не смогли завладеть крупнейшим городом Литвы. Война продолжалась: тевтонские рыцари наносили удары вверх по Неману и разоряли самогитские поселения, но предпринять новый поход в холмистые земли центральной Литвы, тем более к ее столице, им было не под силу. Литовцы оборонялись, ожидая своего часа. Они не могли рисковать всем в открытом сражении и не имели причин переносить военные действия на территорию Пруссии. По крайней мере, в тот момент.