Có bằng chứng về việc các thương nhân Hồi giáo Ả Rập vào Indonesia ngay từ thế kỷ thứ 8.^{[19] [20]} Tuy nhiên, phải đến cuối thế kỷ 13, đạo Hồi mới bắt đầu lan rộng.^[19] Lúc đầu, đạo Hồi được du nhập thông qua các thương nhân Hồi giáo Ả Rập, sau đó là hoạt động truyền giáo của các học giả.Nó còn được hỗ trợ thêm bởi sự chấp nhận của những người cai trị địa phương và sự chuyển đổi của giới tinh hoa.^[20] Các nhà truyền giáo có nguồn gốc từ một số quốc gia và khu vực, ban đầu từ Nam Á (tức là Gujarat) và Đông Nam Á (tức là Champa), ^[21] và sau đó từ phía nam bán đảo Ả Rập (tức là Hadhramaut).^[20]Vào thế kỷ 13, các chính thể Hồi giáo bắt đầu xuất hiện ở bờ biển phía bắc Sumatra.Marco Polo, trên đường từTrung Quốc về nhà vào năm 1292, đã báo cáo rằng có ít nhất một thị trấn Hồi giáo.^[22] Bằng chứng đầu tiên về một triều đại Hồi giáo là tấm bia mộ, có niên đại năm 1297 CN, của Sultan Malik al Saleh, người cai trị Hồi giáo đầu tiên của Vương quốc Samudera Pasai.Đến cuối thế kỷ 13, Hồi giáo đã được thành lập ở Bắc Sumatra.Đến thế kỷ 14, Hồi giáo đã được hình thành ở đông bắc Malaya, Brunei, tây nam Philippines , và trong một số triều đình ven biển phía Đông và Trung Java, và đến thế kỷ 15, ở Malacca và các khu vực khác của Bán đảo Mã Lai.^[23] Thế kỷ 15 chứng kiến ​​sự suy tàn của Đế chế Majapahit của người Java theo đạo Hindu, khi các thương nhân Hồi giáo từ Ả Rập,Ấn Độ , Sumatra và Bán đảo Mã Lai, cũng như Trung Quốc bắt đầu thống trị thương mại khu vực từng được kiểm soát bởi các thương nhân Majapahit của người Java.Triều đại nhà Minh của Trung Quốc đã hỗ trợ có hệ thống cho Malacca.Các chuyến đi của nhà Minh Trung Quốc Zheng He (1405 đến 1433) được cho là đã tạo ra khu định cư của người Hồi giáo Trung Quốc ở Palembang và bờ biển phía bắc Java.^[24] Malacca tích cực khuyến khích việc chuyển đổi sang đạo Hồi trong khu vực, trong khi hạm đội nhà Minh tích cực thành lập cộng đồng người Hồi giáo gốc Hoa-Malay ở ven biển phía bắc Java, do đó tạo ra sự phản đối lâu dài đối với người theo đạo Hindu ở Java.Đến năm 1430, các đoàn thám hiểm đã thành lập các cộng đồng người Hoa, người Ả Rập và người Mã Lai theo đạo Hồi ở các cảng phía bắc Java như Semarang, Demak, Tuban và Ampel;do đó, Hồi giáo bắt đầu có được chỗ đứng ở bờ biển phía bắc Java.Malacca thịnh vượng dưới sự bảo hộ của nhà Minh, trong khi Majapahit liên tục bị đẩy lùi.^[25] Các vương quốc Hồi giáo thống trị trong thời gian này bao gồm Samudera Pasai ở phía bắc Sumatra, Vương quốc Malacca ở phía đông Sumatra, Vương quốc Demak ở miền trung Java, Vương quốc Gowa ở miền nam Sulawesi, và các vương quốc Ternate và Tidore ở Quần đảo Maluku ở phía đông.