Praktik haji sesungguhnya sudah ada sejak ratusan tahun lalu ada di negeri ini. Bagi muslim zaman dahulu dengan yang hidup diera sekarang hasrat untuk menyempurnakan rukun Islam kelima ini tak ada bedanya, tak akan pernah surut meski harus menempuh risiko dan medan yang sangat berat. Haji bukan sekadar perjalanan wisata biasa, tetapi bertanda seorang muslim menjadi muslim paripurna.
Lalu siapa anak nusantara yang pertama kali naik haji? Pertanyaan ini memang tak mudah dijawab. Sebab ternyata praktik haji berbanding lurus dengan sejarah islamisasi nusantara. Sayangnya tidak terlalu banyak catatan sejarah yang menunjukkan secara pasti kapan persisnya orang nusantara naik haji, karena rata-rata catatan haji baru mulai ditulis pada abad 19.
Dalam buku”Naik Haji di Masa Silam” yang ditulis Henry Chambert Loir memiliki catatan yang cukup baik dan dapat dipertanggungjawabkan. Catatan Raja Pasai memeluk Islam (akhir abad 13) menjadi pembuka pintu lorong gelap sejarah haji di nusantara disusul peristiwa Raja Malaka masuk Islam (tahun 1430-an).
Zaman Sultan Mansyur Syah (1459-1477) dia begitu ingin naik haji maka itu dia menyiapakan puluhan kapal dan 12 ton emas dan permata dia benar-benar ingin berangkat ke Mekkah. Namun sayang niatnya tak kesampaian karena keburu terserang sakit kemudian meninggal. Puteranya, Sultan Alaudin Riayat Syah (1477-1488) coba meneruskan cita-cita mendiang ayahnya. Tapi sayang, setelah persiapan begitu matang dalam perjalanan dari Bintan ke Malaka dia juga tak memiliki umur panjang menyusul ayahnya menghadap Yang Maha Pencipta.
Sultan Mahmud Syah penerus kedua sultan tersebut ternyata berbeda seratus delapan puluh derajat. Dia malah ’anti’ Mekkah. Menurutnya tak perlu jauh-jauh naik haji ke Mekkah sebab Malaka ’derajatnya’ sama dengan Mekkah.
Dalam catatan sejarah orang yang pertama naik haji adalah Laksamana Hang Tuah. Tokoh yang banyak memiliki kelebihan ini berangkat haji ketika ditugaskkan oleh Sultan Malaka ke Istambul untuk membeli senjata meriam. Dia membawa rombongan besar dengan 42 kapal yang mengangkut 1600 prajurit dengan armadanya yang dikenal dengan nama Menfam Berahi.
Hang Tuah naik haji bertepatan dengan 9 Dzulhijjah 866 atau 29 januari 1482. Ketika itu yang mejadi ’Raja Mekkah’ adalah Syarif Ahmad bin Zainal Abidin, sedangkan Madinah dipimpin oleh saudaranya Syarif Baharudin. Tapi catatan haji Hang Tuah ini banyak mendapat kritik karena ada beberapa peristiwayang tidak sinkron.