The period of Islamic influence in Southeast Asia was, in actual fact, a period of Arabic influence modified by Indian ideas. This was so because Islam came to Malaysia through India and the same type of people who introduced Hinduism to Malaysia at the beginning of the Christian era also introduced Islam to this part of the world.

Like its predecessor, Hindu religion and culture, Islam was also synonymous with the Indian trade. Like its predecessor too, the spread of Islam was not the result of any organised missionary movement; rather, it was a gradual and perhaps unconscious assimilation of an Asian religion by Asian peoples who were impressed by the introduction of the first monotheistic religion.

The preceding religions, primitive paganism and Hinduism, had been polytheistic. Hindu culture and religion had come from the Coromandel coast of India, notably from the Port of Amaravathi, at the mouth of the river Kistna. With the spread of Islam from about the 13th century A.D., the centre of radiation moved to the Malabar coast, especially to Gujerat in the West and Bengal in the East. By virtue of their financial standing, the Gujerat and Bengali merchants drew large numbers of converts in the ports in which they traded. As in the case of the Hindu religion, the first converts were from the aristocratic class. Once Islam had set a foot-hold among the rulers and chiefs of the coastal commercial areas and these rulers had set their seal of authority on the new faith, immediately it became acceptable to the common people.

The spread of Islam was greatly enhanced partly by social contact as a consequence of trade, but more important still, by marriages. In a few decades, the Javanese, Sumatran, Malay and other aristocracies of the coastal districts had gone over to the new faith. The common people followed in gradual stages down the social scale. Diplomatic marriages between aristocracies of different kingdoms spread the faith even further. A notable example was the marriage of the first Muslim Sultan of Pasai on the North-Western coast of Sumatra who died in 1297 A.D., to a daughter of the ruler of Perlak, also on the northern coast of Sumatra. The powerful Sultanate of Malacca too, arranged many such diplomatic marriages with Borneo, Pahang and Kedah and with the Sumatran river ports of Siak, Kampar, Inderagiri and Jambi.

As early as 1281 A.D., Chinese chronicles record an embassy led by two Muslims from Jambi or Melayu in Sumatra to the Mongol court. This indicates that Islam must have reached the northern coast of Sumatra well before that date. Another source of information about the beginning of the spread of Islam in the Malay Archipelago is provided by Marco Polo. He visited the port of Perlak, which he called "Felech", on the Northern coast of Sumatra in 1292 A.D. on his return voyage to Europe through the Straits of Malacca Marco Polo remarked in his later writings that many of the inhabitants of Perlak had at that time been converted to Islam by the foreign merchants who frequently called there. Pasai on the north-western coast of Sumatra whose first Muslim ruler died in 1297, five years after Marco Polo's visit to Perak, provided probably the first foothold for Islam in Sumatra.

In the Malay Peninsula, the first physical evidence of the arrival of Islam was found at a spot twenty miles up the Trengganu river. There, a stone inscribed with Arabic letters has been found, dating as far back as 1386 or probably 1326 A.D. This evidence of the existence of Islam in Malaysia's east coast perhaps initiated the theory that Islam came to Malaysia through China.

At the close of the 14th century when Islam was spreading in conjunction with the prospering Indian trade, the nucleus of a new and powerful Malay kingdom and empire was taking shape. This was to replace the decaying might of the Hindu-Javanese empire of Majapahit and become the first powerful Muslim empire in the region - Melaka. With its rapid rise as a commercial port of call during the first quarter of the 15th century, Malacca became the spearhead of the further advance of Islam - an advance achieved by growing commercial power and consolidated by judicious royal marriages - spreading the faith to the ports of Java and Borneo from whence it was spread yet further eastward as far as the Moluccas.