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