Genoese there, besieging Kaffa in 1397. In late 1397 or early 1398, Tokhtamysh briefly triumphed over his rivals, taking over Sarai and the Volga towns, and sent out jubilant missives through his envoys all round. But his success was short-lived: Tokhtamysh was defeated in battle by Tīmūr Qutluq and fled first to the Crimea, where he was met with hostility, then via Kiev to Grand Prince Vytautas of Lithuania. Vytautas settled Tokhtamysh and his followers near Vilnius and Trakai, although many of them abandoned him, making their way to the Balkans to enter the service of the Ottoman sultan Bayezit I. Tokhtamysh and Vytautas signed a treaty in which Tokhtamysh confirmed Vytautas as a rightful ruler of Ruthenian lands that were once part of the Golden Horde, and now belonged to Lithuania, and promised him the tribute of the Russian principalities, in exchange for military assistance to recover his throne. Possibly the treaty still stipulated that Vytautas would pay tribute from these the Ruthenian lands once the khan regained his throne. Vytautas was possibly planning to establish himself as overlord in the lands of the Golden Horde. Exile Tīmūr Qutluq sent an envoy to demand Tokhtamysh's extradition from Lithuania, but received an ominous answer from Vytautas: "I will not give up Tsar Tokhtamysh, but wish to meet Tsar Temir-Kutlu in person." Vytautas and Tokhtamysh prepared their Lithuanian and Mongol forces for a joint campaign, supported by Polish volunteers under Spytek of Melsztyn. In the summer of 1399, Vytautas and Tokhtamysh set out against Tīmūr Qutluq and Edigu with a large army. On the Vorskla River they encountered the forces of Tīmūr Qutluq, who opened negotiations, intending to delay the engagement until Edigu could arrive with reinforcements. In the process, Tīmūr Qutluq pretended to agree to submit to Vytautas and pay him annual tribute but requested a three-day delay to consider Vytautas' further demands. This was sufficient for Edigu to arrive with his reinforcements. Edigu could not resist the temptation to bandy words with the Lithuanian ruler himself, and arranged a meeting, separated by the course of the river. Further negotiations having proven pointless, the two forces engaged in the Battle of the Vorskla River on 12 August 1399. Using a feigned retreat tactic, Tīmūr Qutluq and Edigu were able to envelop the forces of Vytautas and Tokhtamysh, inflicting a serious defeat on them. Tokhtamysh fled the battlefield and made his