There is evidence of Arab Muslim traders entering Indonesia as early as the 8th century.^{[19] [20]} However, it was not until the end of the 13th century that the spread of Islam began.^[19] At first, Islam was introduced through Arab Muslim traders, and then the missionary activity by scholars. It was further aided by the adoption by the local rulers and the conversion of the elites.^[20] The missionaries had originated from several countries and regions, initially from South Asia (i.e. Gujarat) and Southeast Asia (i.e. Champa),^[21] and later from the southern Arabian Peninsula (i.e. Hadhramaut).^[20]

In the 13th century, Islamic polities began to emerge on the northern coast of Sumatra. Marco Polo, on his way home from China in 1292, reported at least one Muslim town.^[22] The first evidence of a Muslim dynasty is the gravestone, dated CE 1297, of Sultan Malik al Saleh, the first Muslim ruler of Samudera Pasai Sultanate. By the end of the 13th century, Islam had been established in Northern Sumatra.

By the 14th century, Islam had been established in northeast Malaya, Brunei, the southwestern Philippines, and among some courts of coastal East and Central Java, and by the 15th century, in Malacca and other areas of the Malay Peninsula.^[23] The 15th century saw the decline of the Hindu Javanese Majapahit Empire, as Muslim traders from Arabia, India, Sumatra and the Malay Peninsula, and also China began to dominate the regional trade that was once controlled by Javanese Majapahit traders. Chinese Ming dynasty provided systematic support to Malacca. Ming Chinese Zheng He's voyages (1405 to 1433) is credited for creating Chinese Muslim settlement in Palembang and north coast of Java.^[24] Malacca actively encouraged the conversion to Islam in the region, while Ming fleet actively established Chinese-Malay Muslim community in northern coastal Java, thus creating a permanent opposition to the Hindus of Java. By 1430, the expeditions had established Muslim Chinese, Arab and Malay communities in northern ports of Java such as Semarang, Demak, Tuban, and Ampel; thus, Islam began to gain a foothold in the northern coast of Java. Malacca prospered under Chinese Ming protection, while the Majapahit were steadily pushed back.^[25] Dominant Muslim kingdoms during this time included Samudera Pasai in northern Sumatra, Malacca Sultanate in eastern Sumatra, Demak Sultanate in central Java, Gowa Sultanate in southern Sulawesi, and the sultanates of Ternate and Tidore in the Maluku Islands to the east.