Wyjście ekspedycji na Saharę rozpoczęło się 16 października 1590 roku. Przeprawa przypadała na porę zimową, co wpływało korzystnie na szanse jej powodzenia. Nie zmienia to faktu, że przedsięwzięcie było bardzo trudne – na pustynnej trasie liczącej ponad 1100 kilometrów jedynie co 200–300 kilometrów znajdowały się źródła wody. Przemarsz trwał 135 dni – 1 marca 1591 roku Dżaudar dotarł do miejscowości Karabara nad rzeką Niger. Ciężkie warunki tułaczki przez pustynię przetrwała tylko połowa sił marokańskich. Władca Songhaju, Askia Ishak II nie wykorzystał szansy uderzenia na wycieńczoną armię. Choć wiedział o marokańskiej wyprawie, to przypuszczał początkowo, iż zginie ona w trakcie drogi, a potem, że wojska paszy uderzą najpierw na Timbuktu.
Dżaudar skierował się w stronę stolicy Songhaju – Gao. Askia postanowił pokonać wroga w walnej bitwie dzięki przytłaczającej przewadze liczebnej. Zebrał armię liczącą według różnych szacunków ogółem 25 tysięcy ludzi lub też 30000 pieszych i 12500 konnych. Strony starły się 12 marca 1591 w zaciętej bitwie pod Tondibi. Toczyła się ona ze zmiennym szczęściem od 9 rano do 15. Zakończyła się ona zdecydowanym zwycięstwem armii paszy.