Dari Samudra Pasai mereka berlayar ke India atau Maladewa. Dua route pelayaran tinggal dipilih: menuju pelabuhan Hormuz di Teluk Persia atau pelabuhan Aden di Yaman, yang merupakan tempat konsentrasi penganut mazab Syafii.
Tidak heran apabila duta Timur Lenk untuk India pada awal abad ke-15 M mencatat dalam kitab sejarahnya bahwa pada awal abad ke-15 M banyak sekali kapal-kapal dari pulau Jawa dan Sumatra berlabih di Hormus, Iran sekarang ini.
Dari Aden dan Hormuz ini orang-orang yang naik haji berangkat ke Mekkah melalui jalan darat. Adapun yang berlabuh di pelabuhan Hormuz meneruskan perjalanan darat menuju Baghdad.
Dalam Hikayat Hang Tuah dipaprkan orang-orang Melayu banyak yang naik haji dengan terlebih dahulu berkumpul di kota Baghdad. Yaitu di Mesjid Syekh Abdul Qadir Jailani yang merupakan markas Tariqat Qadiriyah.
Di kota ini, sebelum menuju Mekkah, Syekh Hamzah Fansuri dibaiat sebagai mursyid tariqat Qadiriyah di Nusantara. Setelah menunaikan ibadah haji ia melanjutkan perjalanan ke Yerusalem atau al-Quds. Seperti ditulis dalam syair tasawufnya:
Hamzah Fansuri di dalam Makkah
Mencari Tuhan di Baitil Ka’bah
Di Barus ke Quds terlalu payah
Akhirnya jumpa dalam rumah