Foreign Muslims had traded in Indonesia and China for many centuries; a Muslim tombstone in eastern Java bears a date corresponding to 1082. But substantial evidence of Islam in Indonesia begins only in northern Sumatra at the end of the 13th century. Two small Muslim trading kingdoms existed by that time at Samudra- Pasai and Perlak. A royal tomb at Samudra, of 1297, is inscribed entirely in Arabic. By the 15th century the beachheads of Islam in Indonesia had multiplied with the emergence of several harbour kingdoms, ruled by local Muslim princes, on the north coast of Java and elsewhere along the main trading route as far east as Ternate and Tidore in the Moluccas.

The establishment of the first Muslim centres in Indonesia was probably a result of commercial circumstances. By the 13th century, in the absence of a strong and stable entrepôt in western Indonesia, foreign traders were drawn to harbours on the northern Sumatran shores of the Bay of Bengal, distant from the dangerous pirate lairs at the southern end of the Strait of Malacca. Northern Sumatra had a hinterland rich in gold and forest produce, and pepper was being cultivated at the beginning of the 15th century. It was accessible to all archipelago merchants who wanted to meet ships from the Indian Ocean. By the end of the 14th century, Samudra-Pasai had become a wealthy commercial centre, giving way in the early 15th century to the better protected harbour of Malacca on the southwest coast of the Malay Peninsula. Javanese middlemen, converging on Malacca, ensured its importance.

Pasai's economic and political fame depended almost entirely on foreigners. Muslim traders and teachers were probably associated with its administration from the beginning and were bound to introduce the religious institutions that made foreign Muslims feel at home. The first Muslim beachheads in Indonesia, and especially Pasai, were to a considerable extent genuine Muslim creations that commanded the loyalty of the local population and encouraged scholarly activities. There were similar new harbour kingdoms on the northern coast of Java. Tomé Pires, author of the Suma Oriental, writing not long after 1511, stresses the obscure ethnic origins of the founders of Cheribon, Demak, Japara, and Gresik. These Javanese kingdoms existed to serve the commerce with the extensive Muslim world and especially with Malacca, an importer of Javanese rice. The rulers of Malacca, though of prestigious Palembang origin, had accepted Islam precisely in order to attract Muslim and Javanese traders to their port.

Arab trader arriving in Indonesia.

New men could now be expected to contribute impulses to Indonesian life. The northern Sumatran and Javanese coasts seem hitherto to have been on the fringe of the Shaivite-Mahayana cultures of southern Sumatra and eastern Java. For the first time in Indonesian history, the possibility existed that the inhabitants of formerly peripheral regions would begin to influence the course of events, inspired by Islam's assertion of the equality of all believers and supported by very profitable communications with the Muslim world throughout Asia.

But Indonesian history is the history of many distinct and often greatly separated regions. The history of early Indonesian Islam is no exception. What happened in the 15th and 16th centuries cannot be explained simply in terms of the influence of new ideas. The political ambitions of many regional princes intervened, and a variety of often rapidly changing and sometimes disturbed situations developed. The historian looks in vain for a uniform pattern of early Muslim life in the archipelago.

Aceh (Acheh), which succeeded Pasai in the 16th century as the leading harbour kingdom in northern Sumatra, became a self-consciously Muslim state, though a persuasive case has been made for the persistence as late as the 17th century of "Hindu" notions of divine kingship familiar in Java. Aceh had contacts with Muslim India and its own heterodox school of Muslim mysticism; its sultans sought an alliance with the Ottoman Turks against the Portuguese, who had conquered Malacca in 1511. The Malay princes of Malacca installed Muslim vassals on the east coast of Sumatra in the 15th century, but when Malacca was captured by the Portuguese the princes transferred their capital southward to Johore and gradually became involved in a conflict not only with the Portuguese but also with the Achinese for control of the Strait of Malacca. Aceh, for its part, was unable to impose its faith on the Batak highlanders in the interior. The single and notable gain for Islam in Sumatra was in the Minangkabau country, where Shaivite-Mahayana Tantric cults had flourished in the 14th century. Islam's penetration of Minangkabau by way of the Achinese west coast of Sumatra was far advanced by the beginning of the 17th century. Minangkabau, a land of enterprising and mobile traders, was later to exercise a significant influence in the affairs of the archipelago.