8ویں صدی کے اوائل میں عرب مسلم تاجروں کے انڈونیشیا میں داخل ہونے کے شواہد موجود ہیں۔^{[19] [20]} تاہم، 13ویں صدی کے آخر تک اسلام کا پھیلاؤ شروع نہیں ہوا تھا۔^[19] سب سے پہلے، اسلام کو عرب مسلمان تاجروں کے ذریعے متعارف کرایا گیا، اور پھر علماء کی طرف سے مشنری سرگرمی۔اسے مقامی حکمرانوں کی طرف سے اپنانے اور اشرافیہ کی تبدیلی سے مزید مدد ملی۔^[20] مشنریوں کی ابتدا کئی ممالک اور خطوں سے ہوئی تھی، ابتدا میں جنوبی ایشیا (یعنی گجرات) اور جنوب مشرقی ایشیا (یعنی چمپا) سے، ^[21] اور بعد میں جنوبی جزیرہ نما عرب (یعنی حدرموت) سے۔^[20]13ویں صدی میں، سماٹرا کے شمالی ساحل پر اسلامی سیاست کا ظہور ہونا شروع ہوا۔مارکو پولو، 1292 میںچین سے گھر جاتے ہوئے، کم از کم ایک مسلم قصبے کی اطلاع دی۔^[22] ایک مسلم خاندان کا پہلا ثبوت قبر کا پتھر ہے، جو کہ 1297 عیسوی میں، سلطان ملک الصالح کا ہے، جو سمودیرا پسائی سلطنت کے پہلے مسلمان حکمران تھے۔13ویں صدی کے آخر تک اسلام شمالی سماٹرا میں قائم ہو چکا تھا۔14ویں صدی تک، اسلام شمال مشرقی ملایا، برونائی، جنوب مغربی فلپائن ، اور ساحلی مشرقی اور وسطی جاوا کی کچھ عدالتوں میں، اور 15ویں صدی تک، ملاکا اور جزیرہ نما مالائی کے دیگر علاقوں میں قائم ہو چکا تھا۔^[23] 15ویں صدی میں ہندو جاوانی مجاپاہت سلطنت کا زوال دیکھنے میں آیا، کیونکہ عرب،ہندوستان ، سماٹرا اور جزیرہ نما مالے کے مسلمان تاجروں اور چین نے بھی علاقائی تجارت پر غلبہ حاصل کرنا شروع کر دیا جو کبھی جاوانی مجاپاہت تاجروں کے زیر کنٹرول تھا۔چینی منگ خاندان نے ملاکا کو منظم مدد فراہم کی۔منگ چینی زینگ ہی کے سفر (1405 سے 1433) کو پالمبنگ اور جاوا کے شمالی ساحل میں چینی مسلمانوں کی آباد کاری کا سہرا دیا جاتا ہے۔^[24] ملاکا نے خطے میں اسلام قبول کرنے کی فعال طور پر حوصلہ افزائی کی، جبکہ منگ بحری بیڑے نے شمالی ساحلی جاوا میں چینی-مالائی مسلم کمیونٹی کو فعال طور پر قائم کیا، اس طرح جاوا کے ہندوؤں کی مستقل مخالفت پیدا ہوئی۔1430 تک، مہمات نے جاوا کی شمالی بندرگاہوں جیسے سیمارنگ، ڈیمک، توبان، اور امپل میں مسلمان چینی، عرب اور مالائی کمیونٹیز قائم کر دی تھیں۔اس طرح اسلام نے جاوا کے شمالی ساحل پر قدم جمانا شروع کر دیا۔ملاکا چینی منگ کے تحفظ کے تحت خوشحال ہوا، جبکہ مجاپہیت کو مسلسل پیچھے دھکیل دیا گیا۔^[25] اس وقت کے دوران غالب مسلم سلطنتوں میں شمالی سماٹرا میں سمودیرا پاسائی، مشرقی سماٹرا میں ملاکا سلطنت، وسطی جاوا میں ڈیماک سلطنت، جنوبی سولاویسی میں گووا سلطنت، اور مشرق میں جزائر مالوکو میں ترنیٹ اور تیڈور کی سلطنتیں شامل تھیں۔