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