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