Московский князь сумел по-своему воспользоваться этим походом. Зная, что основные силы Орды были отвлечены на Литву, Василий Дмитриевич послал большую рать на Волжскую Болгарию. Были взяты города: Болгары, Жукотин, Казань, Кременчук. Через три месяца московская армия возвратились домой с большой добычей.
Тем временем в Киеве Витовт собрал огромное войско: кроме руси, литвы, жмуди и тохтамышевых татар здесь были полки волошские, польские и немецкие. Одних князей летописцы насчитывают до пятидесяти.
Еще в 1398 году «Тахтамышев царев посол Темирьхозя был на Рязани у великого князя Олега Ивановича Рязанского, а с ним много татар и коней и гостей». Возможно, посол прибыл с предложением выступить на стороне Витовта и Тохтамыша против тогдашнего хана Золотой Орды Темир-Кутлуя. Если так, то Олег, очевидно, отказал, т. к. в 1399 году он не принимал участия в сражении у реки Ворсклы. Это и неудивительно, Олег не мог простить Витовту набегов на Рязань и захвата Смоленска.
Перед выступлением Витовта в поход к нему прибыл посол Темир-Кутлуга с требованием выдать ему Тохтамыша. Но великий князь литовский передал в ответ: «Хана Тохтамыша не выдам, а с ханом Темир-Кутлуем хочу видеться сам».
18 мая 1399 года войско Витовта выступило в поход. Но только 5 августа армия достигла реки Ворсклы, где их уже встречали татары. За почти 3 месяца похода Витовт прошел чуть больше 300 км! С такой «мобильной» армией он дошел бы до Сарая ровно за год.
Навстречу великой армии Витовта вышел татарский хан Темир-Кутлуг. На помощь к хану уже спешил эмир Едигей. Ожидая подмоги, хан вступил с Витовтом в переговоры. Послы Темир-Кутлу-га спросили от имени хана у Витовта: «За что идешь на меня? Я не вступал никогда на твою землю с оружием!» Витовт расценил это как слабость противника и в ответ высокомерно заявил: «Бог покорил мне все земли, покорись и ты, будь мне сыном, а я тебе буду отцом, и плати мне ежегодно дань; а не захочешь быть сыном, так будешь рабом, и вся Орда твоя будет предана огню».
Ожидая подхода Едигея и желая потянуть время, Темир-Кут-луг согласился платить Витовту дань и признал его отцом. Великий князь литовский, видя такую уступчивость, настолько обнаглел, что выдвинул новое дерзкое требование: «Во всей Орде быть на деньгах ордынских знамению Витовта». То есть он потребовал, чтоб хан Золотой Орды признал над собой власть Литвы и стал печатать на своих деньгах знак великого князя литовского.
Темир-Кутлуг не отказался прямо чеканить на своих монетах изображения Витовта и литовский герб, но попросил три дня на размышления для окончательного ответа, и Витовт дал ему эти три дня. Тем временем к хану Темир-Кутлугу подходили союзники. Пришел и эмир ногайской орды Едигей с большим войском. Переговоры тут же приняли другой оборот. Узнав об амбициях Витовта, Едигей пожелал лично увидеться с ним. Они съехались на противоположных берегах Ворсклы, и Едигей насмешливо начал свою речь: «Князь храбрый, наш царь справедливо мог признать тебя отцом, он моложе тебя годами, но зато я старше тебя, а потому теперь ты признай меня отцом, изъяви покорность и плати дань, а также изобрази на литовских деньгах мою печать». Едигей также потребовал у Витовта: «Выдай мне царя беглого Тохтамыша, ибо он враг мой, и не могу я терпеть, слыша, что он жив и у тебя живет».
Слова эмира привели Витовта в ярость, и он приказал тотчас же готовиться к битве. Краковский воевода Спытко, видя большое число воинов у Едигея (по некоторым явно завышенным данным их было около 200 тысяч человек), советовал Витовту не вступать в бой, а попытаться замириться с татарами. Однако остальные воеводы возмутились его словам, причем один из польских панов, некто Щуковский, хвастливо упрекнул Спытко: «Если тебе жаль расстаться с твоей красивой женой и с большими богатствами, то не смущай по крайней мере тех, которые не страшатся умереть на поле битвы». На это Спытко с достоинством ответил ему: «Сегодня же я паду честной смертью, а ты трусливо убежишь от неприятеля». Предсказание его сбылось.
12 августа начался бой, в результате которого истощенные Тамерлановым разгромом татары Золотой Орды без особого труда разбили огромную армию, объединявшую силы почти всей Восточной Европы. «Побили татары на том великом побоище много князей литовских и воевод, и бояр великих, и христиан много и Литвы, и Немец, и Ляхов, и иных людей многое множество бесчисленное пало тогда, и мало осталось их».
Видя, что литовцы проигрывают, Тохтамыш первым обратился в бегство и, отступая с поля боя, принялся по дороге грабить литовские земли. Он справедливо счел, что раз литовцы проиграли битву, то их земли все равно будут ограблены татарами. Так пусть уж будут воины Тохтамыша! Потом Тохтамыш со всей своей родней и военными силами откочевал из владений Витовта в неизвестном направлении.