Pada akhir abad ke-13 M, kerajaan Samudera Pasai secara pasti mulai berdiri seiring dengan kemunduran Sriwijaya. Dalam masa ini, kekuasaan Islam di luar wilayah Nusantara justru menunjukkan kemunduran yang luar biasa—dinasti Amawiyah Andalus sedang terdesak ke selatan, dinasti Fati-miyah tengah mengalami kemunduran dan perang Salib masih berlangsung, serta hancurnya dinasti Abbasiyah di Baghdad pada tahun 1258 oleh Hulagu Khan—.

Munculnya Samudera Pasai sebenarnya merupakan akibat arus balik peranan pedagang Muslim Timur Tengah di wilayah Nusantara. Oleh karena itu, tidak mengherankan jika sentimen religio-kultural yang menghubungkan antara Timur Tengah dan Nusantara kemudian berkembang melewati batas-batas ajaran formal Islam.

Para penguasa Muslim di Sumatra dan Semenanjung Malaya—tempat Islam pertama kali menancapkan akar terkuatnya—, sering mengasosiasikan diri mereka dengan kekuasaan-kekuasaan politik besar di Timur Tengah, mulai dari kerajaan Samudera Pasai, kerajaan Perlak, hingga kerajaan Aceh. 

Hubungan politik antara Timur Tengah dengan Nusantara tampak nyata ketika Sultan Ali Mughayyat Syah (1511-1530 M), sultan pertama kerajaan Aceh, mengadakan hubungan dengan dinasti Turki Utsmani yang tampil sebagai kekuatan politik Islam terbesar di Dunia Muslim. 

Hubungan ini jelas sangat diwarnai solidaritas keagamaan dalam menghadapi Portugis (kaum Kristen) yang sejak tahun 1521 M menguasai pelabuhan Pasai. Dalam hal ini, Turki Utsmani membantu Aceh untuk mengusir Portugis. 

Selanjutnya, Sultan Aceh, Ala al-Din Riayat Syah al-Kahhar (1537-1571 M), melakukan langkah formal untuk tunduk secara sukarela pada kekuasaan dinasti Turki Utsmani sebagai balasan atas bantuan militer yang diberikan kepada Aceh. 

Langkah ini tampaknya didasari oleh kebutuhan kerajaan Aceh atas sekutu yang kuat. Tidak hanya untuk mengusir Portugis dari Malaka, tetapi juga untuk memperluas kekuasaan kerajaan Aceh ke wilayah-wilayah lain, khususnya daerah pedalaman di Sumatera. 

Pada perkembangan berikutnya, di bawah pemerintahan Sultan Iskandar Muda (1607-1637 M), kerajaan Aceh meraih kejayaan politiknya. Kontrol kerajaan begitu efektif atas seluruh pelabuhan penting di pantai barat dan di pantai timur Sumatra.

Selain mendominasi jaringan perdagangan maritim di pelabuhan-pelabuhan tersebut, kerajaan Aceh juga melakukan kontrol atau penguasaan di bagian-bagian tertentu Semenanjung Malaya, yaitu Pahang, Kedah, dan Perlis. Semua perkembangan ini—sedikit banyak—disebabkan oleh bantuan yang diberikan dinasti Turki Utsmani, baik penasihat-penasihat militer, senjata, maupun amunisi. 

Hubungan antara kerajaan-kerajaan Nusantara dengan Timur Tengah tidak terbatas pada Dinasti Turki Utsmani. Kerajaan Aceh, misalnya, juga menjalin hubungan dengan pusat keagamaan Islam, yakni Makkah dan Madinah (Haramayn). 

Meskipun hubungan ini lebih bersifat keagamaan ketimbang politik, namun hubungan penguasa Aceh dengan penguasa Haramayn mempunyai implikasi politik yang penting bagi kerajaan Aceh. Dari hubungan ini, selain menerima “stempel emas”, sejak tahun 1570-an kerajaan Aceh secara reguler menerima ulama-ulama terkemuka dari Hijaz. 

Kemudian sejak abad ke-17 M, seiring dengan kemunculannya, beberapa kerajaan Muslim di wilayah Nusantara menjalin hubungan dengan Hijaz untuk meneguhkan kekuasaan mereka. Pada tahun 1638 M, penguasa Banten di Jawa Barat, Abd al-Qadir (1626-1651 M), mendapat gelar “Sultan” dari Syarif Makkah sebagai hasil misi khusus yang dikirimkannya ke Tanah Suci. 

Selanjutnya Mataram, sebuah kerajaan besar Muslim di pulau Jawa, juga merasakan kebutuhan untuk menjalin hubungan yang erat dengan Syarif makkah, dan sekaligus untuk mendapatkan gelar sultan dari penguasa Tanah Suci ini. Untuk tujuan terakhir ini, penguasa Mataram, Pangeran Rangsang, mengirim delegasi ke Makkah pada tahun 1641 M. Duta Mataram itu menumpang kapal Inggris ke Surat, India; dan dari sana dengan kapal Muslim menuju Jeddah.

Seperti bisa diduga, Syarif Makkah memenuhi keinginan Pangeran Rangsang dan memberikan gelar Sultan kepadanya. Pangeran Rangsang sejak saat itu lebih dikenal sebagai Sultan Agung, salah seorang penguasa terbesar Mataram. Sultan Agung, yang sangat bersyukur atas anugerah yang dilimpahkan penguasa Haramayn kepadanya, pada tahun berikutnya mengirim sekelompok orang Jawa membawa hadiah kepada Syarif Makkah dan sekali-gus menunaikan haji atas namanya. 

Di samping penguasa kerajaan Aceh, kerajaan Banten, dan kerajaan Mataram, beberapa penguasa Muslim Nusantara lainnya juga diketahui pernah menerima surat-surat dari penguasa Haramayn, termasuk penguasa Palembang dan penguasa Makassar. Pengiriman surat-surat melalui pihak ketiga, seperti dalam kasus kerajaan Palembang, dan pengiriman dua orang mullah dari Makkah ke Makassar, mengindikasikan terdapatnya orang-orang Nusantara dari masing-masing wilayah itu di Makkah. 

Mereka, bisa jadi adalah para pedagang atau jamaah haji yang memperpanjang masa tinggal me-reka di Makkah untuk berdagang dan menuntut ilmu. Selain itu juga memainkan peran sebagai duta-duta kerajaan mereka di Haramayn. 

Para penguasa Haramayn setidaknya sejak abad ke-16 M, tampaknya telah mengenal baik Muslim Nusantara. Dalam hal ini, kerajaan-kerajaan Muslim Nusantara, khususnya Aceh, turut membantu kehidupan para penguasa Haramayn dan penuntut ilmu di Tanah Suci dengan berbagai hadiah yang mereka kirimkan. 

Dengan begitu, penguasa Haramayn sebaliknya, dapat memberikan dukungannya kepada para penguasa Muslim Nusantara.

Surat-surat dan hadiah-hadiah semacam itu dipandang para penguasa dan kaum Muslim Nusantara umumnya memiliki aura kesucian yang bersumber dari tempat paling suci dalam tradisi Islam. Hal ini tentu saja memberikan implikasi yang cukup penting, terutama dalam memberikan legitimasi bagi kekuasaan para penguasa di mata kaum Muslim Nusantara.