Приняв решение, Витовт начал тщательную подготовку к походу, который, он надеялся, закончится завоеванием Золотой Орды. Он обратился за помощью и к Польше, и к рыцарям Тевтонского ордена. Король Польши Ягайло согласился предоставить несколько воинских соединений, но значительно меньше, чем Витовт ожидал. Чтобы получить поддержку рыцарей, Витовт уступил им часть территорий племени жмудь. Из этих соображений они согласились послать отборный и хорошо вооруженный отряд для участия в кампании841. Мы не располагаем информацией о переговорах Витовта с Москвой, но, в любом случае, Москва оставалась нейтральной. Великий князь Василий Московский имел, безусловно, серьезные основания относиться с подозрительностью к намерениям своего тестя. В 1395 году Витовт захватил Смоленск и заключил под стражу большинство удельных князей этого княжества. Поскольку Смоленск не подчинялся Москве, великий князь московский был обеспокоен усилением литовского контроля над ним. Еще более угрожающим являлось намерение Витовта установить свой сюзеренитет над Новгородом. В 1398 году он договорился с Тевтонским орденом о совместном походе против Пскова и Новгорода. В случае успеха рыцари получали Псков, а Витовт – Новгород. Теперь эти планы отменились из-за нового поворота в монгольских делах.

Основная часть сил Витовта в степной кампании 1399 года состояла из литовской и западнорусской армии и татар Тохтамыша. Литовско-русская армия была хорошо организована и имела на вооружении пушки. Правители Золотой Орды тоже хорошо подготовились к войне. Вместо того, чтобы ждать врага глубоко в степях, как это сделал Субэдэй в 1223 году, Тимур-Кутлуг и Едигей решили продвинуться к среднему течению Днепра в киевском направлении. В начале августа 1399 года две враждующие армии встретились на берегах Ворсклы (приток Днепра), вероятно, недалеко от того места, где однажды будет построен город Полтава, и Петр Великий в 1709 году разобьет шведов.

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

Преследуя остатки побежденной армии Витовта, Тимур-Кутлуг дошел прямо до Киева и разбил перед городом свой лагерь. Отряды его армии рассеялись по всей Киевской земле и Подолии, грабя города и селения и захватывая тысячи пленников. Киев должен был уплатить 3 000 рублей выкупа. Бассейн нижнего Буга, завоеванный Ольгердом в 1363 году и дававший Литве выход к Черному морю, теперь снова был занят монголами и отведен под пастбища для части Ногайской Орды Едигея.

Даже после этой катастрофы Тохтамыш не оставил своих попыток вернуть власть в кипчакских степях. Витовт предложил воинам Тохтамыша земельные наделы в Литве, если они пойдут к ч нему на службу. Хотя многие из них приняли предложение, Тохтамыш вернулся в степи с небольшим отрядом верных единомышленников и начал против Едигея партизанскую войну. После поражений в нескольких столкновениях, он ушел на восток и нашел пристанище в Тюмени в западной Сибири843. Оттуда он отправил посла своему бывшему сюзерену Тимуру, еще раз испрашивая покровительства и предлагая союз против Едигея. Тимур милостиво принял посла Тохтамыша в городе Отрар в январе 1405 года. Тимур тогда стоял на пороге своего нового похода против Китая. Его, вне всякого сомнения, беспокоил быстрый подъем сил Едигея и, чтобы предотвратить возможность нападения Едигея на Центральную Азию во время его отсутствия, он был рад использовать Тохтамыша против Едигея, как он использовал Едигея против Тохтамыша десять лет назад. Ни Тимуру, ни Тохтамышу не суждено было воспользоваться плодами их нового союза. Тимур скончался в Отраре 18 февраля 1405 года. Тохтамыш, по-видимому, умер в Тюмени примерно в то же время или вскоре после того. В любом случае, его имя не упоминается после этой даты в доступным нам источниках.

Едигей принадлежал к древней монгольской семье рода Белых мангкытов (Ак-Мангкыт)844. Мангкыты, как мы знаем, составляли ядро Ногайской Орды. Их поддержка серьезно помогла Едигею при захвате власти в Золотой Орде – как и Ногаю примерно 130 лет назад. Однако положение Едигея было сложнее, чем положение Ногая, поскольку он не являлся Чингисидом. Правда, он объявлял себя потомком, через прародительницу, первого халифа Абу-Бакра845. Для мусульман это, по-видимому, было достаточно весомо. Но, хотя большая часть монгольских князей и знати к этому времени и приняла ислам, они не отказывались от всех своих монгольских традиций. Политически теперь, как и раньше, только за потомками Чингисхана признавалось право на трон Золотой Орды. Едигей, таким образом, находился в том же положении, что Мамай и Тамерлан. Единственным для него выходом было управлять через марионеточных ханов. Сам он вынужден был удовлетвориться титулом эмира. Тимур-Кутлуг, первый хан, которого он посадил на трон, был пьяницей и умер в 1400846. Затем с одобрения Едигея ханом избрали его двоюродного брата Шадибека847. Согласно персидскому историку Муин ад-дин Натанзи, Шадибек всю свою жизнь проводил в пирах и удовольствиях848. Сначала Едигей не испытывал никаких затруднений в управлении через него.

Разбив армию Витовта и отрезав Литву от Черного моря, Едигей сосредоточился на восстановлении порядка и дисциплины в Золотой Орде. Как формулирует Муин ад-дин, он установил «изысканные обычаи и великие законы»849. Под первыми он, вероятно, подразумевает строгие церемониальные формы повиновения знати хану; под вторыми Ясу со всеми ее дополнениями, включая жестокую систему налогообложения. Интересным аспектом политики Едигея была попытка прекратить торговлю рабами-тюрками. Еще до монгольского нашествия половецких детей продавали в Египет, где их готовили для отрядов мамлюков. Эта практика сохранялась в конце тринадцатого века и весь четырнадцатый. Теперь, согласно аль-Макризи, Едигей запретил «татарам» продавать своих детей в рабство за границу850. Под татарами Макризи, судя по всему, имеет в виду не только половцев, но и всех других тюркизованных граждан Золотой Орды. Едигей, видимо, хотел предотвратить уменьшение численной силы тюрков как основы Золотой Орды. В результате этой политики количество рабов, поставляемых в Сирию и Египет из Золотой Орды, резко сократилось. Позже такая торговля возродилась, но продавали уже не тюркских детей, а черкесских851. Необходимо подчеркнуть, что политику Едигея в этом случае нельзя истолковывать как желание свернуть внешнюю торговлю вообще. Напротив, он прекрасно осознавал важность развития торговли в Золотой Орде, и, в особенности, восстановления торговых путей в Центральную Азию. Воспользовавшись смертью Тамерлана (1405 год), он в 1406 году захватил Хорезм852.