Det finns bevis på att arabiska muslimska handlare kom in i Indonesien så tidigt som på 800-talet.^{[19] [20]} Det var dock inte förrän i slutet av 1200-talet som spridningen av islam började.^[19] Till en början introducerades islam genom arabiska muslimska handlare, och sedan missionsverksamhet av forskare.Det fick ytterligare hjälp av adoptionen av de lokala härskarna och omvandlingen av eliten.^[20] Missionärerna hade sitt ursprung från flera länder och regioner, till en början från Sydasien (dvs Gujarat) och Sydostasien (dvs Champa) ^{[, 21]} och senare från den södra Arabiska halvön (dvs. Hadhramaut).^[20]På 1200-talet började islamisk politik växa fram på Sumatras norra kust.Marco Polo, på väg hem frånKina 1292, rapporterade om minst en muslimsk stad.^[22] Det första beviset på en muslimsk dynasti är gravstenen, daterad CE 1297, av sultan Malik al Saleh, den första muslimska härskaren över Samudera Pasai Sultanate.I slutet av 1200-talet hade islam etablerats på norra Sumatra.På 1300-talet hade islam etablerats i nordöstra Malaya, Brunei, sydvästra Filippinerna och bland några domstolar i östra och centrala Java vid kusten och på 1400-talet i Malacka och andra områden på den malaysiska halvön.^[23] På 1400-talet försvagades det hinduiska javanesiska Majapahitriket, då muslimska handlare från Arabien,Indien , Sumatra och Malayhalvön, och även Kina började dominera den regionala handeln som en gång kontrollerades av javanesiska Majapahithandlare.Kinesiska Ming-dynastin gav systematiskt stöd till Malacka.Ming kinesiska Zheng Hes resor (1405 till 1433) krediteras för att ha skapat kinesisk muslimsk bosättning i Palembang och Javas norra kust.^[24] Malacka uppmuntrade aktivt omvandlingen till islam i regionen, medan Ming-flottan aktivt etablerade kinesisk-malayisk muslimsk gemenskap i norra kusten på Java, vilket skapade en permanent opposition mot Javas hinduer.År 1430 hade expeditionerna etablerat muslimska kinesiska, arabiska och malaysiska samhällen i norra hamnar på Java som Semarang, Demak, Tuban och Ampel;därmed började islam få fotfäste på Javas norra kust.Malacka blomstrade under kinesiskt Ming-skydd, medan Majapahit stadigt pressades tillbaka.^[25] Dominerande muslimska kungadömen under denna tid inkluderade Samudera Pasai på norra Sumatra, Malacca-sultanatet i östra Sumatra, Demak-sultanatet i centrala Java, Gowa-sultanatet i södra Sulawesi och sultanaterna Ternate och Tidore på Malukuöarna i öster.