Daar is bewyse van Arabiese Moslem-handelaars wat Indonesië so vroeg as die 8ste eeu binnegekom het.^{[19] [20]} Dit was egter eers aan die einde van die 13de eeu dat die verspreiding van Islam begin het.^[19] Aanvanklik is Islam ingevoer deur Arabiese Moslem-handelaars, en toe die sendingaktiwiteit deur geleerdes.Dit is verder aangehelp deur die aanneming deur die plaaslike heersers en die bekering van die elite.^[20] Die sendelinge het uit verskeie lande en streke gekom, aanvanklik uit Suid-Asië (dws Gujarat) en Suidoos-Asië (dit is Champa), ^[21] en later van die suidelike Arabiese Skiereiland (dws Hadhramaut).^[20]In die 13de eeu het Islamitiese politiek aan die noordelike kus van Sumatra begin ontstaan.Marco Polo, op pad huis toe vanChina in 1292, het ten minste een Moslemdorp aangemeld.^[22] Die eerste bewys van 'n Moslem-dinastie is die grafsteen, gedateer CE 1297, van Sultan Malik al Saleh, die eerste Moslem-heerser van Samudera Pasai Sultanaat.Teen die einde van die 13de eeu was Islam in Noord-Sumatra gevestig.Teen die 14de eeu was Islam gevestig in die noordooste van Malaya, Brunei, die suidwestelike Filippyne , en tussen sommige howe van die kus van Oos- en Sentraal-Java, en teen die 15de eeu, in Malakka en ander gebiede van die Maleise Skiereiland.^[23] Die 15de eeu het die agteruitgang van die Hindoe-Javanese Majapahit-ryk gesien, aangesien Moslem-handelaars uit Arabië,Indië , Sumatra en die Maleise Skiereiland, en ook China die streekhandel begin oorheers het wat eens deur Javaanse Majapahit-handelaars beheer is.Chinese Ming-dinastie het stelselmatige ondersteuning aan Malakka gebied.Ming Chinese Zheng He se reise (1405 tot 1433) word gekrediteer vir die skep van Chinese Moslem-nedersettings in Palembang en noordkus van Java.^[24] Malakka het aktief die bekering tot Islam in die streek aangemoedig, terwyl die Ming-vloot aktief Chinees-Maleisiese Moslem-gemeenskap in die noordelike kus van Java gevestig het en sodoende 'n permanente opposisie teen die Hindoes van Java geskep het.Teen 1430 het die ekspedisies Moslem-Chinese, Arabiese en Maleise gemeenskappe in die noordelike hawens van Java soos Semarang, Demak, Tuban en Ampel gevestig;dus het Islam 'n vastrapplek in die noordelike kus van Java begin kry.Malacca was voorspoedig onder Chinese Ming-beskerming, terwyl die Majapahit geleidelik teruggestoot is.^[25] Oorheersende Moslem-koninkryke in hierdie tyd het Samudera Pasai in noordelike Sumatra, Malacca-sultanaat in oostelike Sumatra, Demak-sultanaat in sentraal-Java, Gowa-sultanaat in suidelike Sulawesi en die sultanate van Ternate en Tidore in die Maluku-eilande in die ooste ingesluit.