Но старший из смоленских князей, Юрий, оставался на свободе, в Рязани, и в конце 1395 года тесть его Олег вместе с ним и другими князьями опустошил литовские владения; но еще не успел Олег возвратиться в Рязань, как услыхал, что Витовт пустошит его собственные волости. Тогда, оставив свою добычу в надежном месте, Олег ударил врасплох на литовцев, рассеявшихся для грабежа, и поразил их; Витовт испугался и ушел домой. Великий князь московский при всех этих событиях явно держал сторону тестя: в 1396 году он ездил на свидание с ним в Смоленск, праздновал здесь пасху, я когда рязанский князь снова вошел с полками в землю Литовскую и осадил Любутск, то Василий отправил к нему посла и отвел его от того города. Потом, когда Витовт вошел в рязанские владения и пролил здесь кровь, как воду, по выражению летописей, и людей побивал, сажая их улицами, то из Москвы не было ему никакого препятствия, напротив, зять встретил его в Коломне, поднес дары и оказал большую честь. Мы видели, что в 1397 году оба князя, и московский и литовский, заодно посылали требовать от новгородцев, чтоб те разорвали мир с немцами; но тогда же московский князь мог узнать, какого союзника он имел в своем тесте, ибо в то же время Витовт требовал от новгородцев, чтобы те поддались ему; получивши отказ, он послал в 1399 году в Новгород грамоту разметную (объявление войны) и велел сказать новгородцам: «Вы меня обесчестили: что было вам мне поддаться, а мне было вашим князем великим быть и вас оборонять: но вы мне не поддались». Но не один Витовт объявлял свои притязания на Новгород: еще в 1389 году приехал туда князь Симеон-Лугвений Олгердович, был принят новгородцами с честию и за эту честь дал брату своему королю Ягайлу следующую запись: «Так как господин Владислав (Ягайло), король польский, литовский, русский и иных земель многих господарь, поставил нас опекуном над мужами и людьми Великого Новгорода, то мы королю и Ядвиге королеве вместе с новгородцами обещались и обещаемся, пока держим Новгород в нашей опеке, быть при короне Польской и никогда не отступать от нее».
Намерение Витовта овладеть Новгородом обнаруживается и в договоре его с Орденом в 1398 году; здесь Витовт обещался Ордену помогать ему в завоевании Пскова, за что Орден с своей стороны обязался помогать Витовту в завоевании Великого Новгорода. Но война с последним была отложена, потому что Витовт обратил внимание на дела ордынские, вмешательство в которые обещало ему выгоды более важные. По удалении Тамерлана на юг Тохтамыш попытался было снова утвердиться в Золотой Орде, но был изгнан ханом Темир-Кутлуем (Kotlogh-Timur) и отдался в покровительство Витовту, который обещал ему возвратить Кипчак с тем, чтобы Тохтамыш потом помог ему овладеть Москвою.
В 1399 году Витовт собрал огромное войско; кроме руси, литвы, жмуди и татар Тохтамышевых здесь были полки волошские, польские и немецкие, ибо и находившийся тогда в мире с Витовтом великий магистр Ордена прислал ему отряд войска; одних князей летописцы насчитывают до пятидесяти. Перед выступлением в поход к Витовту явились послы от Темира-Кутлуя. «Выдай мне беглого Тохтамыша, – велел сказать ему хан, – он мой враг, не могу оставаться в покое, зная, что он жив и у тебя живет, потому что изменчива жизнь наша: нынче хан, а завтра беглец, нынче богат, завтра нищий, нынче много друзей, а завтра все враги. Я боюсь и своих, не только что чужих, а хан Тохтамыш чужой мне и враг мой, да еще злой враг; так выдай мне его, а что ни есть около его, то все тебе». Витовт велел отвечать на это: «Хана Тохтамыша не выдам, а с ханом Темир-Кутлуем хочу видеться сам». На берегах Ворсклы произошло это свидание, в поле чистом, в земле Татарской. Но перед битвою начались опять переговоры; Темир-Кутлуй послал сказать Витовту: «Зачем ты на меня пошел? Я твоей земли не брал, ни городов, ни сел твоих». Витовт велел отвечать: «Бог покорил мне все земли, покорись и ты мне, будь мне сыном, а я тебе буду отцом, и давай мне всякий год дани и оброки; если же не хочешь быть сыном, так будешь рабом, и вся орда твоя будет предана мечу». Испуганный хан соглашался на все требования Витовта, который, видя такую уступчивость, начал требовать, чтоб на деньгах ордынских чеканилось клеймо литовского князя; хан просил три дня срока подумать. Но в это время пришел к нему Эдигей; старик, узнавши об условиях, сказал хану: «Лучше нам умереть, чем согласиться на них», – и послал к Витовту требовать личных переговоров; литовский князь выехал на берег Ворсклы, и Эдигей стал ему говорить с другого берега: «По праву взял ты нашего хана в сыновья, потому что ты стар, а он молод; но я старше еще тебя, так следует тебе быть моим сыном, дани давать каждый год, клеймо мое чеканить на литовских деньгах». Витовт рассвирепел и велел немедленно полкам своим сходиться на битву. Сначала полки Витовтовы схватились с полками Эдигеевыми; с обеих сторон стреляли из самострелов и пищалей; но пушки и пищали плохо действовали в чистом поле. Несмотря на то, Витовтова рать крепко боролась, падали стрелы как дождь, и стали полки Витовтовы перемогать князя Эдигея. Но в это время обошли кругом полки Темир-Кутлуевы, вступили в битву и одолели силу литовскую. Тохтамыш первый обратился в бегство и в этом бегстве много народа побрал и много Литовской земли пограбил. Победители взяли весь обоз Витовта, который едва успел убежать с небольшою дружиною; татары гнались за ним пятьсот верст до самого Киева: ставши под этим городом, Темир-Кутлуй распустил свою силу воевать Литовскую землю, и ходила татарская рать до самого Луцка, опустошив все на своем пути. Киев откупился тремя тысячами рублей, причем Печерский монастырь заплатил от себя 30 рублей, и хан ушел в степи, оставив Литовскую землю в плаче и скудости: летописец насчитывает между убитыми с лишком 20 князей.