Напуганные демонстрацией военной мощи Литвы, клятву на верность Витовту принесли мелкие княжества, которые находились в верховьях реки Ока. Василий Московский вынужден был согласиться с этими изменениями. Государственная граница между Московским и Литовским княжествами отныне проходила по реке Угра, левому притоку Оки.
В этот период силы Золотой Орды, Литвы и Москвы стали примерно равны. Своему сыну Василию Дмитрий Московский передал Великое княжество Владимирское в наследство как личную вотчину. Татары смирились с этим, так как сил на новое покорение Руси у них уже не было. В Москву переехал из Владимира митрополит «всея Руси» Киприан.
Москва вступала в эпоху борьбы за русские земли, находившиеся под властью Великого княжества Литовского. Но пока эта борьба велась в скрытой форме. Василий Московский не отваживался бросить прямой вызов своему могущественному тестю. Ни Москва, ни Литва не были готовы к продолжительной войне. Поэтому, несмотря на принудительное крещение Литвы в католичество, даже митрополит Киприан предпочел не портить отношения с великим князем литовским.
Золотая Орда продолжала оставаться союзником Литовского княжества. В 1396 году Тамерлан разгромил войска хана Тохтамыша, а затем и опустошил его кочевья. Потеряв власть, Тохтамыш укрылся во владениях Витовта. Литовский князь использовал насильственное свержение Тохтамыша как повод для нескольких опустошительных рейдов в Северное Причерноморье. Витовт заявлял, что хочет вернуть Тохтамышу его законные владения. На самом же деле он хотел включить в состав своих владений население причерноморских торговых факторий. Витовт желал получить выход в Черное море. Это способствовало бы расцвету литовской торговли и экономики.
В конце XIV века Великое княжество Литовское занимало наибольшую в своей истории территорию — около миллиона квадратных километров. Владения Витовта, который все меньше считался с Ягайло, простирались от Немана и Двины до низовий Днестра и Днепра.
В 1397 году Витовт задумал колоссальную авантюру — он вознамерился присоединить к своим владениям часть провинций Золотой Орды, а также новгородские, псковские земли и Великое княжество Владимирское. Для этого он собирался возвести на трон Золотой Орды хана Тохтамыша. Тохтамыш обещал в случае успеха выдать Витовту татарский ярлык на все эти земли. Витовт передал хану-изгнаннику в кормление Лидский замок и начал готовиться к походу.
Во всех европейских дворах гонцы Витовта объявили о том, что великий князь планирует величайший поход всего христианского мира против неверных. Это сообщение произвело большой резонанс во всей Европе. Папа римский освятил проект литовского князя как крестовый поход.
К войску Великого княжества Литовского присоединились польские рыцари во главе со Спыткой Мелынтинским, полузависимые от Витовта господари Молдавии и Валахии. Даже Тевтонский орден прислал на помощь Витовту крупный отряд. Витовт пригласил участвовать в походе и зятя, Василия Московского. Но московский князь владел гораздо более полной информацией о настоящем военном потенциале Золотой Орды, поэтому предусмотрительно отказался от этой авантюры.
На одном из пиров в 1398 году литовские бояре провозгласили Витовта «королем Литвы и Руси». По сути, это означало фактическую ликвидацию как условий Кревской унии 1385 года, так и условий договора между Витовтом и Ягайлой в 1392 году. Однако окончательно решить этот сложный вопрос Витовт собирался уже после возвращения из похода против ордынцев.
К весне 1399 года в Киеве, где Витовтом был назначен общий пункт сбора, собралось большое войско — около 20 тысяч рыцарей и много артиллерии. В начале лета эта армия под командованием великого князя литовского двинулась к границам Золотой Орды. Московский летописец писал, что в походе Витовта участвовало 50 князей. Вместе с собой Витовт взял всю высшую знать Великого княжества Литовского, даже старших братьев — Андрея и Дмитрия, которым в это время уже исполнилось за семьдесят.
Безусловно, отправляясь в этот поход, Витовт переоценил собственные силы и недооценил могущество противника. Хану Тимур-Кутлуку, который свергнул Тохтамыша, подчинялась гигантская территория Золотой Орды от Причерноморья до Иртыша. Его поддерживал сам Тамерлан, властелин половины Азии.
Большое татарское войско ожидало европейских рыцарей на самой границе — на реке Ворскле. Хан Тимур-Кутлук начал переговоры, соглашаясь на большие уступки. На самом же деле он ожидал подкрепление — войско полководца Тамерлана — Эдигея. Витовт выдвигал все большие требования. Переговоры затягивались.
Но едва к татарскому войску прибыло подкрепление, как тон Тимур-Кутлука резко переменился. Отныне ни о каких уступках Великому княжеству Литовскому не могло идти и речи. Старые литовские полководцы, предчувствуя неизбежный разгром, предлагали Витовту отступить, заключив для приличия с татарами почетный мир. Однако польские рыцари посчитали это предложение позорным. Поляков поддержали молодые литовские рыцари. Витовт отважился на сражение.