По просьбе великого князя Витовта римский папа Бонифаций IX распорядился проповедовать в Польше и Литве, а также «всех окрестных землях» крестовый поход против татар. Сбор всех войск был назначен в Киеве. Поляки, боясь резкого усиления Витовта, от участия в походе уклонились, прислав, как и Орден, символический отряд.
В середине мая 1399 года объединенное войско Витовта и Тохтамыша в несколько десятков тысяч воинов вышло из Киева. 5 августа два войска встали друг против друга на месте впадения реки Ворсклы в Днепр. Темир-Кутлуг, ожидая подхода орды своего союзника хана Эдигея, начал ложные переговоры. Через три дня подошли войска Эдигея и татар стало намного больше, чем войск Витовта и Тохтамыша.
Битва началась утром 12 августа 1399 года. Через несколько часов боя татары Эдигея и Темир-Кутлуга подавили войска Витовта численным преимуществом. Первым побежали татары Тохтамыша, затем воины Витовта, из пятидесяти князей погибло двадцать. В битве погиб и герой Куликовской битвы 1380 года князь Дмитрий Боброк-Волынский, сражавшийся на стороне сына Кейстута. В сражении был смертельно ранен и хан Золотой Орды Темир-Кутлуг. Битва закончилась полным поражением Витовта.
Витовт с отрядом ближних бояр сумел степями все же добраться до Киева и организовать оборону. Подошедшим татарам Эдигея заплатили большой выкуп и они ушли домой с множеством пленных, полностью разорив украинские земли.
Витовту пришлось восстанавливать утраченное, на время отложить реализацию своих планов по строительству и укреплению государства. Он попытался сблизиться с Ягелло и отправился в Краков.
Перед началом поездки в столицу Польши внешнеполитические обстоятельства резко изменились – умерла королева Ядвига и позиция Ягелло в Польше сильно пошатнулась. Тут же великий магистр Ордена отправил Вильгельму Австрийскому предложение предъявить свои права на польский трон, которые будут поддержаны Орденом. Разбитый Витовт и «неустойчивый» Ягелло сблизились. Витовт сразу же отправил великому магистру послание, в котором он заявил о полном согласии с польским королем. Прошло совсем немного времени и Ягелло удалось укрепить свою власть. В январе 1401 года Витовт подтвердил грамотой обещание верности и покорности королю польскому и Польской Короне, от которого за это получил в пожизненное владение Великое княжество Литовское. В случае смерти Витовта наследниками власти в Литве становились Ягелло и его наследники.
