Как только Тимур удалился в Самарканд, упорный Тохтамыш устремился обратно в кипчакские степи и попытался восстановить свою державу. Сначала он направился в Крым, который, по-видимому, решил сделать своей основной базой. Благодаря географическому положению, Крымский полуостров можно защитить даже от превосходящего врага. Во время разгрома 1395 года власть в Крыму захватили генуэзцы[838]. Тохтамыш атаковал силы генуэзцев и штурмом взял Каффу, где, вероятно, захватил значительные богатства. Он, безусловно, нуждался в деньгах, чтобы восстановить свою армию и государство. Сначала ему сопутствовал успех, и скоро он выпустил призыв ко всей монгольской знати и князьям, кто еще не возвратился к нему для этого дела. К 1398 году он почувствовал себя достаточно сильным, чтобы восстановить свой контроль над Русью, и отправил посла к князю Олегу Рязанскому.
В этот момент, однако, в Золотой Орде опять началась смута. Соперники Тохтамыша, Тимур-Кутлуг и Едигей, наконец сумели организовать против него мятеж. Большая часть монгольской знати покинула своего суверена и объявила Тимур-Кутлуга новым ханом. Едигей стал соправителем. Оба направили послов к Тимуру, чтобы принести ему заверения в вассальной верности[839]. Тем временем Тохтамыш во главе нескольких тысяч воинов, сохранивших к нему лояльность, поскакал в Киев и попросил великого князя Витовта помочь ему сохранить трон. Тимур-Кутлуг тоже прислал туда послов с требованием выдать Тохтамыша. Витовт, таким образом, оказался перед серьезной проблемой. После совещания с паны-радой Великого княжества он решил принять сторону Тохтамыша. По сути дела, последние несколько лет Витовт и его советники наблюдали за эволюцией монгольской политики со всевозрастающим интересом. Необходимо иметь в виду, что многие литовско-русские князья считали Золотую Орду главным врагом и были готовы поддержать любую попытку как Москвы, так и Литвы бороться против монголов. К этой группе принадлежали князь Андрей Полоцкий, Дмитрий Брянский и Дмитрий Боброк. Как известно, в 1370-тых годах, когда великий князь Дмитрий Московский возглавил русскую оппозицию монголам, все трое поддержали его и приняли активное участие в Куликовской битве. Когда князья Восточной Руси оказались вынуждены еще раз склонить головы перед ханом, князь Андрей возвратился в Полоцк, который тем временем захватил его брат Скиргайло. Тот схватил Андрея и заключил его в крепость в Польше (1386). Когда в 1393 году Андрею удалось бежать, он стал вассалом Витовта. Мы точно не знаем о времени перехода Дмитрия Боброка от великого князя московского к великому князю литовскому; в 1389 году он еще был в Москве и как свидетель подписал завещание Дмитрия Донского, в 1399 году он состоял в свите Витовта. Эти три князя с энтузиазмом отнеслись к антимонгольским планам Витовта.
Зимой 1397-98 годов Витовт повел свою армию вниз по Днепру и, говорят, достиг побережья Черного моря[840]. Местные татарские орды, встреченные им на своем пути, не оказали сколько-нибудь серьезного сопротивления. Весьма вероятно, что они не симпатизировали ханскому правительству (Тохтамыш еще оставался в то время ханом). Тысячи из них сдавались и их расселяли в районе Тракая. Главная цель похода была, кажется, нащупана. В то время Витовт вряд ли ожидал оказаться способным сокрушить монголов. Но гражданская война и просьба Тохтамыша о помощи изменили всю картину. Теперь Витовт мог надеяться, используя Тохтамыша как марионеточного хана, установить свой сюзеренитет над всей Золотой Ордой.
Приняв решение, Витовт начал тщательную подготовку к походу, который, он надеялся, закончится завоеванием Золотой Орды. Он обратился за помощью и к Польше, и к рыцарям Тевтонского ордена. Король Польши Ягайло согласился предоставить несколько воинских соединений, но значительно меньше, чем Витовт ожидал. Чтобы получить поддержку рыцарей, Витовт уступил им часть территорий племени жмудь. Из этих соображений они согласились послать отборный и хорошо вооруженный отряд для участия в кампании[841]. Мы не располагаем информацией о переговорах Витовта с Москвой, но, в любом случае, Москва оставалась нейтральной. Великий князь Василий Московский имел, безусловно, серьезные основания относиться с подозрительностью к намерениям своего тестя. В 1395 году Витовт захватил Смоленск и заключил под стражу большинство удельных князей этого княжества. Поскольку Смоленск не подчинялся Москве, великий князь московский был обеспокоен усилением литовского контроля над ним. Еще более угрожающим являлось намерение Витовта установить свой сюзеренитет над Новгородом. В 1398 году он договорился с Тевтонским орденом о совместном походе против Пскова и Новгорода. В случае успеха рыцари получали Псков, а Витовт – Новгород. Теперь эти планы отменились из-за нового поворота в монгольских делах.