May katibayan ng pagpasok ng mga mangangalakal na Arabong Muslim sa Indonesia noong ika-8 siglo.^{[19] [20]} Gayunpaman, sa pagtatapos ng ika-13 siglo nagsimula ang paglaganap ng Islam.^[19] Noong una, ang Islam ay ipinakilala sa pamamagitan ng mga mangangalakal na Arabong Muslim, at pagkatapos ay ang gawaing misyonero ng mga iskolar.Natulungan pa ito ng pag-ampon ng mga lokal na pinuno at pagbabalik-loob ng mga elite.^[20] Ang mga misyonero ay nagmula sa ilang mga bansa at rehiyon, sa simula ay mula sa Timog Asya (ibig sabihin, Gujarat) at Timog Silangang Asya (ie Champa), ^[21] at nang maglaon ay mula sa timog Arabian Peninsula (ie Hadhramaut).^[20]Noong ika-13 siglo, nagsimulang lumitaw ang mga pulitika ng Islam sa hilagang baybayin ng Sumatra.Si Marco Polo, sa kanyang pag-uwi mula saChina noong 1292, ay nag-ulat ng hindi bababa sa isang bayan ng Muslim.^[22] Ang unang katibayan ng isang dinastiya ng Muslim ay ang lapida, na may petsang CE 1297, ni Sultan Malik al Saleh, ang unang Muslim na pinuno ng Samudera Pasai Sultanate.Sa pagtatapos ng ika-13 siglo, ang Islam ay naitatag sa Hilagang Sumatra.Pagsapit ng ika-14 na siglo, naitatag na ang Islam sa hilagang-silangan ng Malaya, Brunei, sa timog-kanlurang Pilipinas , at sa ilang mga korte ng baybaying Silangan at Gitnang Java, at noong ika-15 siglo, sa Malacca at iba pang mga lugar ng Malay Peninsula.^[23] Nakita ng ika-15 siglo ang paghina ng Hindu Javanese Majapahit Empire, nang ang mga mangangalakal na Muslim mula sa Arabia,India , Sumatra at Malay Peninsula, at gayundin ang Tsina ay nagsimulang dominahin ang rehiyonal na kalakalan na dating kontrolado ng mga mangangalakal ng Javanese Majapahit.Ang dinastiyang Ming ng Tsina ay nagbigay ng sistematikong suporta sa Malacca.Ang mga paglalakbay ni Ming Chinese Zheng He (1405 hanggang 1433) ay pinarangalan para sa paglikha ng pamayanang Chinese Muslim sa Palembang at hilagang baybayin ng Java.^[24] Aktibong hinimok ng Malacca ang pagbabalik-loob sa Islam sa rehiyon, habang aktibong itinatag ng Ming fleet ang pamayanang Tsino-Malay Muslim sa hilagang baybayin ng Java, kaya lumikha ng permanenteng pagsalungat sa mga Hindu ng Java.Noong 1430, naitatag ng mga ekspedisyon ang mga pamayanang Muslim na Tsino, Arabo at Malay sa hilagang daungan ng Java tulad ng Semarang, Demak, Tuban, at Ampel;kaya, ang Islam ay nagsimulang makakuha ng isang foothold sa hilagang baybayin ng Java.Umunlad ang Malacca sa ilalim ng proteksyon ng Chinese Ming, habang ang Majapahit ay patuloy na itinulak pabalik.^[25] Kabilang sa mga nangingibabaw na kaharian ng Muslim sa panahong ito ang Samudera Pasai sa hilagang Sumatra, Sultanate ng Malacca sa silangang Sumatra, Sultanate ng Demak sa gitnang Java, Sultanate ng Gowa sa timog Sulawesi, at ang mga sultanato ng Ternate at Tidore sa Maluku Islands sa silangan.