Der er beviser for, at arabiske muslimske handlende kom ind i Indonesien så tidligt som i det 8. århundrede.^{[19] [20]} Det var dog først i slutningen af ​​det 13. århundrede, at udbredelsen af ​​islam begyndte.^[19] Først blev islam introduceret gennem arabiske muslimske handlende, og derefter missionsaktivitet af lærde.Det blev yderligere hjulpet af adoptionen af ​​de lokale herskere og elitens omvendelse.^[20] Missionærerne var kommet fra flere lande og regioner, først fra Sydasien (dvs. Gujarat) og Sydøstasien (dvs. Champa), ^[21] og senere fra den sydlige Arabiske Halvø (dvs. Hadhramaut).^[20]I det 13. århundrede begyndte islamisk politik at dukke op på Sumatras nordkyst.Marco Polo, på vej hjem fraKina i 1292, rapporterede om mindst én muslimsk by.^[22] Det første bevis på et muslimsk dynasti er gravstenen, dateret CE 1297, af Sultan Malik al Saleh, den første muslimske hersker over Samudera Pasai Sultanatet.I slutningen af ​​det 13. århundrede var islam blevet etableret i det nordlige Sumatra.I det 14. århundrede var islam blevet etableret i det nordøstlige Malaya, Brunei, det sydvestlige Filippinerne og blandt nogle domstole ved kystnære øst- og centrale Java, og i det 15. århundrede i Malacca og andre områder af den malaysiske halvø.^[23] I det 15. århundrede faldt det hinduistiske javanesiske Majapahit-imperium, da muslimske handlende fra Arabien,Indien , Sumatra og den malaysiske halvø, og også Kina begyndte at dominere den regionale handel, der engang var kontrolleret af javanske Majapahit-handlere.Kinesiske Ming-dynastiet ydede systematisk støtte til Malacca.Ming Chinese Zheng Hes rejser (1405 til 1433) er krediteret for at skabe kinesisk muslimsk bosættelse i Palembang og nordkysten af ​​Java.^[24] Malacca opmuntrede aktivt til omvendelse til islam i regionen, mens Ming-flåden aktivt etablerede kinesisk-malaysiske muslimske samfund i den nordlige kyst af Java, og dermed skabte en permanent modstand mod Javas hinduer.I 1430 havde ekspeditionerne etableret muslimske kinesiske, arabiske og malaysiske samfund i de nordlige havne på Java, såsom Semarang, Demak, Tuban og Ampel;således begyndte islam at få fodfæste på Javas nordlige kyst.Malacca trivedes under kinesisk Ming-beskyttelse, mens Majapahit støt blev skubbet tilbage.^[25] Dominerende muslimske kongeriger i denne tid omfattede Samudera Pasai i det nordlige Sumatra, Malacca-sultanatet i det østlige Sumatra, Demak-sultanatet i det centrale Java, Gowa-sultanatet i det sydlige Sulawesi og sultanaterne Ternate og Tidore på Maluku-øerne mod øst.