Литва, как мы помним, в 1386 г. заключила унию с Польшей, закрепленную династическим браком литовского князя Ягайлы и польской королевы Ядвиги. И хотя Ягайло, приняв имя Владислав, начал поддерживать католическую экспансию, ввести Великое княжество Литовское в состав Польского королевства оказалось не так-то просто. Уния очень плохо воспринималась не только огромным большинством православного русского населения, но и представителями языческой литовской знати, желавшей сохранить свою независимость от поляков. Удельные литовские князья боролись с политикой Ягайлы, и бежавший из плена Витовт принял в этой борьбе живейшее участие. К 1392 г. сын Кейстута стал великим князем Литвы и фактически перестал считаться с Ягайлой.
Именно с Витовтом и договорился в 1395 г. Тохтамыш о разделе Московской Руси. Он согласился уступить все русские земли Витовту, с тем чтобы Витовт оказал ему помощь в возвращении престола в Сарае. Витовт же, давно стремясь расширить Великое княжество Литовское за счет присоединения Руси, достиг к этому времени некоторых дипломатических успехов. Так, в 1390 г. великий князь московский Василий I, выполняя данное в плену обещание, женился на дочери Витовта Софье. К моменту соглашения с Тохтамышем Витовт захватил Смоленское княжество, а чуть позднее присоединил к Литве стоявший на Оке город Любутск (около современной Калуги). Поэтому предложение Тохтамыша хорошо вписывалось в далеко идущие планы Витовта. Посадив на престол Золотой Орды «своего» хана, он получил бы реальную возможность покорить Москву.
Договоренность между Витовтом и Тохтамышем, хотя и выгодная для обеих сторон, была, однако, трудноосуществима. Темир-Кутлуг, владевший Золотой Ордой, отнюдь не собирался уступать престол Тохтамышу и потребовал у Витовта выдачи беглеца. Витовт отказал. Законный хан, естественно, находился в союзе с враждебным Тохтамышу Московским княжеством, но Москве не пришлось даже участвовать в вооруженной борьбе коалиций.
Навстречу Витовту и Тохтамышу, которые собрали огромное войско и двинули его в Подолию, вышел сам Темир-Кутлуг с небольшим татарским отрядом. Витовт потребовал безоговорочной капитуляции. У него было около 100 тысяч человек: литовцы, белорусы, поляки и немецкие рыцари. Темир-Кутлуг постарался оттянуть начало битвы, поскольку ожидал, когда к нему на помощь подойдет из причерноморских степей мурза Едигей, и вступил с Витовтом в переговоры. Литовский князь предъявил Темир-Кутлугу требование, согласие на которое по этикету XIV столетия означало полное подчинение: чеканку ордынской монеты с его, Витовта, изображением, — обосновывая необходимость такого шага тем, что он много старше Темир-Кутлуга. «Рассматривая» требования Литвы, татары выиграли время, и подошедший с войском Едигей тоже получил возможность принять участие в «переговорах». Умный мурза ехидно заявил литовцу следующее: «Я понимаю, славный князь, ты старше нашего законного хана Темир-Кутлуга, но ты младше меня, и если уж судить по старшинству, то это ты должен чеканить деньги с моей печатью».