Islam telah berkembang di Kepulauan Melayu sejak abad ke-12. Dalam pelayaran Marco Polo, beliau mencatatkan telah singgah di Perlak, Sumatera Utara pada tahun 1289 Masehi dan mendapati penduduknya telah beragama Islam.
Sejarah Melayu menggambarkan kerajaan Kesultanan Melayu Melaka mempunyai pentadbiran yang teguh dan stabil. Apabila Parameswara menganut agama Islam pada tahun 1414 Masehi dengan gelaran Megat Iskandar Shah, ia turut merancakkan perkembangan Islam di Nusantara, sekaligus menjadikan Melaka sebagai pusat penyebaran Islam di rantau ini.
Justeru, tidak hairanlah orang Melayu telah berlayar ke Mekah untuk menunaikan ibadah haji sejak awal penyebaran agama Islam di kepulauan Melayu.
Tome Pires, seorang penulis Portugis mencatatkan bahawa pemerintah Kesultanan Melayu Melaka iaitu Sultan Mansur Shah (1477-1488) berhasrat mahu menunaikan haji, tetapi impian itu tidak kesampaian apabila baginda mangkat sebelum sempat berangkat ke Mekah.
Begitu juga dengan penggantinya, Sultan Alauddin Riayat Shah (1477 – 1488) yang telah membuat segala persiapan untuk berangkat menunaikan haji. Namun, hasrat baginda tidak kesampaian apabila mangkat terlebih dahulu.
Dalam Hikayat Hang Tuah pula, diceritakan Hang Tuah telah singgah di Mekah untuk menunaikan haji, dan sempat singgah juga di Madinah dan menziarahi makam Rasulullah s.a.w. Hang Tuah ketika itu dalam perjalanan ke Rum (hari ini dikenali sebagai Turki) bagi membeli kelengkapan senjata untuk pertahanan Melaka.
Salah satu tulisan terawal tentang pengembaraan orang Melayu yang menunaikan haji ialah kitab Tuhfat al Nafis yang ditulis sekitar tahun 1960-an. Juga Hikayat Pelayaran Abdullah karangan Munsyi Abdullah yang menceritakan pengalaman menunaikan haji pada tahun 1854.
Pada abad ke-16, semakin ramai orang dari Kepulauan Melayu yang berlayar ke Mekah untuk menunaikan haji. Ini termasuk golongan para ulama. Banyak juga muncul pelabuhan baru di sekitar Kepulauan Melayu yang menjadi pusat persinggahan jemaah haji yang dalam perjalanan ke Mekah.
Sebelum zaman perang dunia ke-2, sudah semakin ramai orang berlayar ke Mekah untuk menunaikan haji terutamanya golongan para pembesar, kerabat diraja,alim ulama dan para ilmuwan. Rakyat biasa ada juga yang pergi ketika itu, namun terpaksa bergolok gadai dan menjual segala harta benda yang ada bagi mengumpul perbelanjaan untuk ke Tanah Suci.
Sewaktu British menguasai Tanah Melayu, mereka melantik Haji Abdul Majid Zainuddin sebagai Pesuruhjaya Jemaah Haji pertama bagi menguruskan segala perkara berkaitan jemaah haji yang ketika itu menggunakan kapal laut untuk ke Tanah Suci.
Dalam catatannya sewaktu menunaikan haji pada tahun 1924, Haji Abdul Majid memberitahu kos pada tahun itu untuk menunaikan ibadah haji adalah sekitar 500 sehingga 600 Ringgit Malaya.
Jemaah akan mula berlayar lima bulan lebih awal iaitu pada bulan Rejab. Ketika itu hanya ada dua pelabuhan untuk berangkat ke Mekah iaitu di Pulau Pinang dan Singapura. Pelayaran mengambil masa antara 13 sehingga 17 hari.
Selepas Tanah Melayu mencapai kemerdekaan, majoriti jemaah haji masih menaiki kapal laut untuk ke Mekah sama ada bertolak dari pelabuhan Klang atau Pulau Pinang. Antara kapal yang terkenal membawa jemaah haji kita ketika itu ialah kapal Malaysia Kita dan Malaysia Raya.
Bermula tahun 1960 – 1970, perkhidmatan kapal terbang ke Tanah Suci mula diperkenalkan. Jemaah yang mempunyai wang lebih memilih kapal terbang kerana tempoh perjalanan lebih pendek. Namun, masih ramai jemaah yang menggunakan khidmat kapal laut.
Kemudian, Prof Diraja Ungku Aziz membuat cadangan agar Tabung Haji ditubuhkan. Pada tahun 1969, terbentuklah Tabung Haji yang menguruskan segala proses berkaitan haji dan juga umrah. Proses menunaikan rukun islam kelima itu menjadi lebih mudah dan teratur. Malah, ia melupuskan tradisi lama bila jemaah terpaksa menjual segala harta yang menyebabkan ‘kemiskinan’ setelah pulang dari Mekah.
Khidmat kapal laut untuk membawa jemaah haji akhirnya dihentikan sepenuhnya pada tahun 1970. Sejak itu, jemaah haji akan ke Mekah melalui udara, bukan lagi melalui jalan laut seperti dahulu.