هناك أدلة على دخول التجار العرب المسلمين إلى إندونيسيا في وقت مبكر من القرن الثامن.^{[19] [20]} ومع ذلك، لم يبدأ انتشار الإسلام إلا في نهاية القرن الثالث عشر.^[19] في البداية تم تقديم الإسلام من خلال التجار العرب المسلمين، ثم النشاط التبشيري من قبل العلماء.وقد ساعده أيضًا تبني الحكام المحليين وتحويل النخب.^[20] نشأ المبشرون من عدة بلدان ومناطق، في البداية من جنوب آسيا (أي غوجارات) وجنوب شرق آسيا (أي تشامبا)، ^[21] وبعد ذلك من جنوب شبه الجزيرة العربية (أي حضرموت).^[20]في القرن الثالث عشر، بدأت الأنظمة السياسية الإسلامية في الظهور على الساحل الشمالي لسومطرة.أبلغ ماركو بولو، وهو في طريقه إلى منزله منالصين عام 1292، عن بلدة إسلامية واحدة على الأقل.^[22] أول دليل على وجود سلالة مسلمة هو شاهد قبر السلطان مالك الصالح، أول حاكم مسلم لسلطنة ساموديرا باساي، والذي يرجع تاريخه إلى عام 1297 م.بحلول نهاية القرن الثالث عشر، تم تأسيس الإسلام في شمال سومطرة.بحلول القرن الرابع عشر، تم تأسيس الإسلام في شمال شرق مالايا وبروناي وجنوب غرب الفلبين وبين بعض المحاكم الساحلية في شرق ووسط جاوة، وبحلول القرن الخامس عشر في ملقا ومناطق أخرى من شبه جزيرة الملايو.شهد القرن ^{[الخامس عشر]} تراجع إمبراطورية ماجاباهيت الهندوسية الجاوية، حيث بدأ التجار المسلمون من شبه الجزيرة العربيةوالهند وسومطرة وشبه جزيرة الملايو، وكذلك الصين، في السيطرة على التجارة الإقليمية التي كان يسيطر عليها تجار ماجاباهيت الجاويون في السابق.قدمت أسرة مينغ الصينية دعمًا منهجيًا لمالاكا.يعود الفضل إلى رحلات تشنغ خه المينغية الصينية (1405 إلى 1433) في إنشاء مستوطنة إسلامية صينية في باليمبانج والساحل الشمالي لجاوة.^[24] شجعت ملقا بشكل فعال التحول إلى الإسلام في المنطقة، في حين أنشأ أسطول مينغ مجتمعًا مسلمًا صينيًا ماليزيًا في شمال جاوة الساحلية، مما خلق معارضة دائمة للهندوس في جاوة.بحلول عام 1430، أنشأت البعثات مجتمعات صينية وعربية وماليزية مسلمة في الموانئ الشمالية لجاوة مثل سيمارانج، وديماك، وتوبان، وأمبل؛وهكذا بدأ الإسلام في الحصول على موطئ قدم في الساحل الشمالي لجاوة.ازدهرت ملقا تحت حماية أسرة مينغ الصينية، في حين تم صد ماجاباهيت بشكل مطرد.^[25] شملت الممالك الإسلامية المهيمنة خلال هذا الوقت ساموديرا باساي في شمال سومطرة، وسلطنة ملقا في شرق سومطرة، وسلطنة ديماك في جاوة الوسطى، وسلطنة جوا في جنوب سولاويزي، وسلطنة تيرنات وتيدور في جزر مالوكو إلى الشرق.