Voor de komst van het vliegtuig maakten bedevaartgangers lange reizen van weken, maanden tot zelfs jaren over land of zee om Mekka te bereiken. Zij volgden daarbij vaak oude handelsroutes. Pelgrims uit India, Nederlands-Indië, Spanje en Marokko reisden vroeger per zeil- en later per stoomschip; bedevaartgangers uit West-Afrika, Iran of Irak moesten savannes, bergen en woestijnen trotseren. Zeker wanneer pelgrims de woestijn doorkruisten reisden zij voor hun veiligheid vaak in groepsverband in pelgrimskaravanen die militaire bescherming boden.

Twee verzamelpunten voor de jaarlijkse hadj-karavanen waren Cairo in Egypte en Damascus in Syrië. In Cairo sloten Noord-Afrikaanse pelgrims aan. Door de straten van de Egyptische hoofdstad trok voor vertrek een processie, met als hoogtepunt een kameel met een mahmal: een baldakijnachtige tentstructuur die als symbool van politiek gezag over Mekka en Medina werd meegedragen in de hadj-karavaan. De route, waarover men zo’n 45-50 dagen deed, liep via de Sinaï langs de Rode Zee-kust naar Medina en Mekka. Sommige pelgrims scheepten zich echter in in Suez en staken vandaar per boot de Rode Zee over naar Djedda. De woestijnreis van Djedda naar Mekka duurde dan enkele dagen.

In de stad Damascus verzamelden zich naast pelgrims uit Istanbul, die dan al een tocht van bijna 40 dagen achter de rug hadden, ook veel andere bedevaartgangers uit het Osmaanse Rijk. De reis naar Mekka duurde dan nog zo’n 40 dagen en volgde de handelsroute die westelijk Arabië al verbond met de Levant voor de islam. Voor de veiligheid en het comfort van pelgrims bouwden de Osmanen, net zoals hun voorgangers, hadj-forten en legden zij water-reservoirs aan. Tussen 1900 en 1908 werd tussen Damascus en Medina een treinspoor aangelegd. Na opening in 1908 verkortte deze Hedjaz-spoorweg de reistijd van Damascus naar Medina tot drie à vier dagen.

In de 19e eeuw was het grootste deel van de pelgrims afkomstig uit Azië. Op verschillende verzamelpunten op Java en Sumatra verzamelden moslims in voormalig Nederlands-Indië zich voor de hadj. Vanaf deze havens scheepte men zich in op (stoom)boten die in enkele weken de Indische Oceaan overstaken en via de Rode Zee in Djedda arriveerden. Onderweg voegden schepen met pelgrims uit Brits-Indië en Maleisië zich bij hen. De oversteek vanuit Indonesië werd eerst gedaan in zeilschepen. Vanaf 1840 verkortte de toename van stoomschepen de reisduur. Doordat het aantal pelgrims sterk toenam, steeg echter ook de kans op overdracht van besmettelijke ziektes.