شواهدی از ورود بازرگانان مسلمان عرب به اندونزی در اوایل قرن هشتم وجود دارد.^{[19] [20]} با این حال، تا پایان قرن سیزدهم بود که گسترش اسلام آغاز شد.^[19] ابتدا اسلام از طریق تجار مسلمان عرب و سپس فعالیت تبلیغی توسط علما مطرح شد.این امر بیشتر با پذیرش توسط حاکمان محلی و تغییر مذهب نخبگان کمک شد.^[20] مبلغان از چندین کشور و منطقه، در ابتدا از جنوب آسیا (یعنی گجرات) و آسیای جنوب شرقی (یعنی چمپا)، ^[21] و بعد از جنوب شبه جزیره عربستان (یعنی حضرموت) سرچشمه گرفته بودند.^[20]در قرن سیزدهم، سیاست های اسلامی در سواحل شمالی سوماترا شروع به ظهور کردند.مارکوپولو در سال 1292 در راه بازگشت ازچین به خانه حداقل یک شهر مسلمان را گزارش کرد.^[22] اولین شواهد از وجود یک سلسله مسلمان، سنگ قبر سلطان ملک الصالح، اولین فرمانروای مسلمان سامودرا پسای، به تاریخ 1297 میلادی است.در پایان قرن سیزدهم، اسلام در شمال سوماترا مستقر شد.تا قرن چهاردهم، اسلام در شمال شرقی مالایا، برونئی، جنوب غربی فیلیپین ، و در میان برخی از دادگاه‌های جاوه ساحلی شرقی و مرکزی، و تا قرن پانزدهم، در مالاکا و سایر مناطق شبه جزیره مالایا تأسیس شد.^[23] قرن پانزدهم شاهد افول امپراتوری ماجاپاهیت هندو جاوه بود، زیرا بازرگانان مسلمان از عربستان،هند ، سوماترا و شبه جزیره مالایی و همچنین چین شروع به تسلط بر تجارت منطقه ای کردند که زمانی توسط بازرگانان ماجاپاهیت جاوه کنترل می شد.سلسله مینگ چین به طور سیستماتیک از مالاکا حمایت کرد.سفرهای مینگ چینی ژنگ هی (1405 تا 1433) به دلیل ایجاد سکونتگاه مسلمانان چینی در پالمبانگ و سواحل شمالی جاوه است.^[24] مالاکا به طور فعال گرویدن به اسلام را در منطقه تشویق کرد، در حالی که ناوگان مینگ به طور فعال جامعه مسلمان چینی-مالایی را در شمال ساحلی جاوه تأسیس کرد، بنابراین مخالفت دائمی با هندوهای جاوه ایجاد کرد.تا سال 1430، اکسپدیشن ها جوامع مسلمان چینی، عرب و مالایی را در بنادر شمالی جاوه مانند سمارنگ، دماک، توبان و آمپل ایجاد کردند.بدین ترتیب، اسلام در سواحل شمالی جاوه جای پای خود را به دست آورد.مالاکا تحت حمایت مینگ چینی پیشرفت کرد، در حالی که ماجاپاهیت به طور پیوسته به عقب رانده شدند.^[25] پادشاهی های مسلمان غالب در این زمان شامل سامودرا پاسای در شمال سوماترا، سلطان نشین مالاکا در شرق سوماترا، سلطان نشین دماک در جاوه مرکزی، سلطان نشین گووا در جنوب سولاوسی، و سلطان نشین های ترنات و تیدور در جزایر مالوکو در شرق بودند.