Kai Aukso Ordos chanai susipyko ir susiskaldė, chanas Tochtamišas (Tegtemas) tapo vieninteliu ordos chanu Rytų Europos šiaurinėje dalyje. Lietuva palaikė glaudus ryšius su juo ir kartu grobdavo kaimynines žemes. Už bendradarbiavimą ir paramą užkariaujant Rusios kunigaikščių žemes Lenkijos karaliui Jogailai 1393 m. jis įteikė jarlyką valdyti Rusios kunigaikščių ir Aukso Ordos užkariautas žemes. Sustiprinęs savo karines pajėgas chanas Tochtamišas norėjo tapti Aukso Ordos valdovu ir nuversti Tamerlaną, bet 1395 m. nugalėti nepavyko ir teko bėgti. Po keletas metų grįžo į Lietuvą ir pasiprašė prieglobsčio. Lietuvos Didysis kunigaikštis Vytautas pasiūlė jam atgauti Aukso Ordos chano sostą iš chano Tamerlano, mainais už tai padėti jam atkovoti Rusios pietvakarių žemes ir Podolę.
1397-1398 m. Lietuvos Didysis kunigaikštis Vytautas su chanu Tochtamišu organizavo kelis žygius į pietus. Dono-Azovo stepėse įsiveržė į Nogajų Ordos valdas ir surinko daug nogajų karių savo tarnybai. Vėliau patraukė į Krymą sutramdė anksčiau Tochtamišui nepaklusnius, o dabar chanui Timur-Kutlugui ir emirui Edygui ištikimus vietos didikus. Krymo pusiasalyje kunigaikštis Vytautas papildė savo vilkstinę vietos totoriais ir karaimais. J. Dlugošo metraštyje minima, kad einančio karavano dydis siekė daug tūkstančių įvairių rangų karių, ginklų, arklių, kinkinių šeimų su moterimis ir vaikais. Kažkokį kiekį nogajų atidavė Lenkijos karaliui Jogailai, dalį paliko dabartinėje Baltarusijoje, likusius apgyvendino netoli Trakų ir Vilniaus – Vokės upelio pakrantėse. Atvežtus iš Krymo karaimus įkurdino Trakuose, o Krymo totorius – Lenkijos ir Lietuvos valdovų žemėse. Taip atsirado pirmosios totorių gyvenvietės LDK, kurių dalis išliko dabartinėse Lenkijos, Baltarusijos ir Lietuvos valstybėse.
Po Vytauto ir Tochtamišo sėkmingo žygio pietuose naujas Aukso Ordos chanas Timur-Kutlugas pareikalavo Vytauto išduoti Tochtamišą ir sudaryti taiką. Jis atsisakė ir pradėjo ruoštis karui, kuris įvyko 1399 m. rugpjūčio 12 d. netoli Kijevo prie Dniepro upės Varsklos upelio. Mūšyje susikovė sutelkta kariuomenė iš Lenkijos, Lietuvos, Vokiečių kryžiuočių ordino ir Tochtamišo totorių būrys prieš Aukso Ordos emiro Edigos armiją. Mūšio pradžioje persvarą turėjo LDK kariai ir sąjungininkai, bet kai prisijungė chano Timur-Kutlugo pagrindinės pajėgos Vytauto sąjungininkų kariuomenė buvo sutriuškinta. Vytautui saugiai pasitraukti iš mūšio lauko padėjo Mamajaus totorių-kazokų palikuonis. Kare žuvo daug drąsių sąjungininkų karių ir 20 karo vadų. Kare žuvo Lietuvos kunigaikščio Algirdo du sūnūs: Polocko kunigaikštis Andrius ir Briansko kunigaikštis Dmitrijus bei daug Tochtamišo karių. Istorikų vertinimu tas pralaimėjimas pristabdė LDK plėtrą į pietines žemes ir Juodosios jūros link.
Europoje žinomas Prūsijos žemėse įvykęs Žalgirio mūšis, kurį kryžiuočiai vadino Tanenbergo kautynėmis. Mūšis įvyko 1410 m. liepos 15 d. tarp Griunfeldo ir Liudviksdorfo kaimelių Prūsijoje, dabar Lenkija. Skaitoma, kad sąjungininkų pusėje buvo apie 20-25 tūkstančių karių su 50 lenkų vėliavomis, 40 lietuvių ir gūdų vėliavomis (vėliavoje virš100 karių), daug totorių, čekų, pulkas karių iš Smolensko, kažkiek moldavų. Vokiečių ordino pajėgos sudarė apie 15 tūkst. šarvuotų riterių iš Vakarų Europos. Tokius skaičius pateikia Lietuvos istorikas A. Bubliauskas (11). Kiti istorikai pateikia didesnius kariaujančiųjų ir žuvusiųjų skaičių, vaizduodami didingesnius mūšio vaizdus. Totorius atsiuntė Aukso Ordos chanas Timūras paprašius kunigaikščiui Vytautui. Totorių būriui vadovavo chano Tochtamišo sūnus Dželal ad-Dinas. Šiame mūšyje LDK kariuomenė su pagalbininkais galutinai sutriuškino Vokiečių Kryžiuočių Ordiną. Ne veltui, po Žagirio karo pralaimėjimo, kryžiuočių vadai teisinosi Romos Popiežiui: ėjo kariauti su lenkais, o kovėsi ir su Azijos totoriais ir pralaimėjo. Po sėkmingo Žalgirio mūšio iš didelio Dželal ad-Dino būrio princų, riterių, murzų ir begų dalis liko pas kunigaikštį Vytautą, papildydami totorių kariuomenės elitą Lietuvoje.
Silpnėjant Aukso Ordos chanų galioms Rytų Europoje ir kylant neramumams ordos viduje totoriai pradėjo ieškoti politinės paramos stipresnėse valstybėse, ankščiau palaikančius su jais gerus santykius. Tokia buvo Vytauto Lietuva. Aidas apie Vytautą kaip karvedį, užkariautų žemių valdovą ir totorių globėją buvo pasiekęs tolimus totorių ulusus. Jie girdėjo apie „balto chano Vattad“ humaniškumą, kad net paimtus priešų belaisvius jis ne žudė, leido gyventi savo žemėse. Be to, iš savo tėvynainių žinojo, kad Vytautas totoriams patiki tarnauti savo kariuomenėje, duoda žemės, leidžia kalbėti savo kalba, išpažinti islamo religiją ir atlikti savo papročius.
Vytautas, tuo laiku, Lietuvoje jautėsi tvirtu šeimininku: tiesė kelius, statė tiltus, tvirtino pilis, kūrė apsauginius postus prie kelių vedančių iš Vilniaus per Trakus, Punią į Žemaitiją ir Prūsiją, iš kur dažnai traukdavo vokiečių kryžiuočių riteriai pulti sostinę. Šių kelių ruože ir žiede galėjo atsirasti totorių kaimų Dzūkijoje, Suvalkijoje ir kitur. Čia vykstantiems kryžiuočiams buvo pirmos kliūtys kelyje, iš čia raiteliai nešė žinias valdovui apie gręsianti pavojų. Todėl šių krypčių keliai kunigaikščiui Vytautui buvo strategiškai svarbūs. Jis netolimose apylinkėse lankėsi, medžiojo ir ilsėjosi Punios žiemos rezidencijoje (buveinėje) su pirmąja žmona Ona. Čia, pas Lietuvos Didįjį kunigakštį Vytautą, lankėsi kitų žemių kunigaikščiai.
Lietuvos Didysis kunigaikštis Vytautas Aukso Ordoje įgavo tokį didelį pasitikėjimą, kad tapo jų teritorijų šeimininku. Kai Burgundijos hercogas paprašė leidimo lankytis Aukso Ordoje jo pasiuntiniui Gilbertui de Lannoy, tai Vytautas išdavė leidimą tiurkų, rusų ir lotynų kalbomis jam keliauti po Aukso Ordos žemes ir parūpino jį lydėti savo ginkluotą apsaugą.
Totorių imigracija į Lietuvą vyko ir po Lietuvos Didžiojo kunigaikščio Vytauto mirties. Po Vytauto mirties tapti Lietuvos karaliumi siekė Lenkijos karaliaus Jogailos jauniausias brolis Švitrigaila. Tam labai pasipriešino Lenkijos karalystės bajorija ir dvasininkija. Savo tikslui pasiekti užtarimo ieškojo pas Šv. sosto imperatorių, karinės paramos prašė Livonijos ordino ir Aukso Ordos. Žinoma, kad jam pagelbėti į Lietuvą atvyko Aukso Ordos kariuomene vadovaujama karvedžio Ulug-Achmedo ir rėmė Švitrigailą kovose su Lenkijos karalystės bajorais. Vyko ilgokas LDK vidaus didikų karas, kuriame Švitrigaila prie Pabaisko 1435 m. galutinai pralaimėjo. Pradžioje, Švitrigailos siekius išlaisvinti Lietuvą nuo Lenkijos vasalinės priklausomybės rėmė Žygimantas Kęstutaitis. Kai Švitrigala buvo apkaltintas išdavystėmis ir neištikimybe karalystei bei stačiatikybės rėmimu, Žygimantas atsisakė jį palaikyti. Tapęs Lietuvos didžiuoju kunigaikščiu atėmė iš jo Lietuvos karalystes pietrytines valdomas žemes ir Ulug-Achmedo totorių karius. Nuo tada totorių kariai rėmė Žygimanto kariuomenę prieš Maskvą, dėl Rusios žemių ir chaną Chadži Girėjų, dėl Krymo chanato sosto. Kai Ulug-Achmedas su būriu karių pasitraukė iš Lietuvos dalis totorių karių pasiliko Lietuvoje.