Det er bevis på at arabiske muslimske handelsmenn kom inn i Indonesia så tidlig som på 800-tallet.^{[19] [20]} Det var imidlertid først på slutten av 1200-tallet at utbredelsen av islam begynte.^[19] Først ble islam introdusert gjennom arabiske muslimske handelsmenn, og deretter misjonsvirksomhet av lærde.Det ble ytterligere hjulpet av adopsjonen av de lokale herskerne og omvendelsen av elitene.^[20] Misjonærene hadde sitt opphav fra flere land og regioner, først fra Sør-Asia (dvs. Gujarat) og Sørøst-Asia (dvs. Champa), ^[21] og senere fra den sørlige arabiske halvøy (dvs. Hadhramaut).^[20]På 1200-tallet begynte islamske politikker å dukke opp på den nordlige kysten av Sumatra.Marco Polo, på vei hjem fraKina i 1292, rapporterte om minst én muslimsk by.^[22] Det første beviset på et muslimsk dynasti er gravsteinen, datert CE 1297, til Sultan Malik al Saleh, den første muslimske herskeren av Samudera Pasai Sultanate.På slutten av 1200-tallet var islam etablert i Nord-Sumatra.På 1300-tallet hadde islam blitt etablert i det nordøstlige Malaya, Brunei, det sørvestlige Filippinene , og blant noen domstoler ved kysten av Øst- og Sentral-Java, og på 1400-tallet i Malacca og andre områder av den malaysiske halvøya.^[23] På 1400-tallet gikk det hinduistiske javanske Majapahit-imperiet tilbake, da muslimske handelsmenn fra Arabia,India , Sumatra og den malaysiske halvøya, og også Kina, begynte å dominere den regionale handelen som en gang var kontrollert av javanske Majapahit-handlere.Kinesiske Ming-dynastiet ga systematisk støtte til Malacca.Ming Chinese Zheng Hes reiser (1405 til 1433) er kreditert for å ha opprettet kinesisk muslimsk bosetning i Palembang og nordkysten av Java.^[24] Malacca oppmuntret aktivt til å konvertere til islam i regionen, mens Ming-flåten aktivt etablerte kinesisk-malayisk muslimsk samfunn i den nordlige kysten av Java, og skapte dermed en permanent motstand mot hinduene på Java.I 1430 hadde ekspedisjonene etablert muslimske kinesiske, arabiske og malaysiske samfunn i nordlige havner på Java som Semarang, Demak, Tuban og Ampel;dermed begynte islam å få fotfeste på den nordlige kysten av Java.Malacca hadde fremgang under kinesisk Ming-beskyttelse, mens Majapahitene ble jevnt presset tilbake.^[25] Dominerende muslimske riker i løpet av denne tiden inkluderte Samudera Pasai i det nordlige Sumatra, Malacca-sultanatet i det østlige Sumatra, Demak-sultanatet i det sentrale Java, Gowa-sultanatet i det sørlige Sulawesi, og sultanatene Ternate og Tidore på Maluku-øyene i øst.