Regular coastal trade in the Persian Gulf and Arabian Sea linking Mesopotamia and the Indus valley dates from at least the time of the Assyrian Empire (729-612 BC). Arab and Persian merchants are reported in the southern Chinese port of Guangzhou (Canton) in the 8th century AD. However, after Mahmud of Ghazni's invasions of the Indus valley (997-1030), the Sword of Islam added a vigorous religious and political dimension to the commerce.
On his return to Venice from the court of Kublai Khan, Marco Polo noted in 1292 that Pasai in northern Sumatra had converted to Islam. The Sultan of Pasai, the first Muslim ruler on Sumatra, died in 1297 and Pasai returned under Majapahit's Hindu ambit in 1350. Despite this reverse, Islam was moving steadily through the archipelago.
Islamic inscriptions in Malaya date from 1326. A Muslim scholar, Mukdum, from Malaya is reported in the Philippine's Sulu archipelago in 1380. In 1400, the northern Sumatran province of Aceh converted to Islam.
When Majapahit captured the Sri Vijayan capital Palembang in 1377, a prince of the royal house, Parameshwara, escaped to Malaya. In 1402 he chose the choke point where the Straits of Malacca narrow to 53 km in width to found his new capital, Melaka. Parameshwara moved quickly to protect his fledgling state. He sent a mission to the Emperor Zhu Di (Yong Li) seeking Ming protection from his Majapahit enemies. Admiral Zheng He (Cheng Ho) arrived at Melaka in 1409 with the Ming's Dragon Fleet. Parameshwara paid a personal visit to Beijing in 1411 to cement his alliance with the Ming Empire.
In the same year as a Muslim mission was attracting converts far to the east on Ambon in the Moluccas, Parameshwara announced his conversion to Islam in 1414 and proclaimed himself Sultan of Malacca. The appeal of Islam was strong. The Sultanate's arch rival, Majapahit converted in 1447. Hindus who wanted to retain their faith were under siege. From mid-century on, Javanese Hindus concentrated on the island of Bali where they have succeeded in preserving their religion to the present day. In 1475 the Moluccan islands of Ternate and Tidore converted to Islam.
Through the 15th century the upstart Sultanate of Malacca grew from strength to strength. It successfully repelled overland and seaborne attacks from the Thai Empire in 1445 and 1456. The Sultan Mansur Shah put down the Thai's peninsular allies Kedah and Pahang in 1459. Finally in 1498, by the efforts of its Admiral Hang Tuah, Malacca had secured the monopoly. All the trade in the Straits, and especially the spices from the Celebes and the Moluccas, moved under its protection and through its markets.
Considering that in over a thousand years, Buddhism and Hinduism had barely made an impression east of Borneo, for Islam to have travelled the length of the archipelago from Sumatra to the Moluccas in under two centuries is remarkable. As a religion, Islam had popular appeal. The Hindu and Buddhist religions had been used mainly to deify the rule of the Rajas. Islam offered its converts a personal salvation.
Islam was also carried with the mobility of the merchant community. The landed Hindu-Buddhist Rajas were content to let the trade come to them and tax it as it passed through their ports. Lacking a fixed land base, the Islamic merchants followed their commercial instincts knowing that the best profits on the trade were to be made at source. The trail of conversions led straight to the spices.
Perhaps most important of all, Islam brought with it gunpowder, firearms and cannon. Recalling how smartly the Sultan of Malacca accepted the new faith and how quickly others followed his lead, access to the new weapons may have been restricted to the faithful. The religion's rapid progress through the islands may have been, at least in part, an arms race.
The year that the Sultanate of Malacca finally consolidated its hold on the Straits was fateful. That same year, Vasco da Gama rounded the Cape of Good Hope from Portugal with four ships, crossed the Indian Ocean and landed on 27 May 1498 at Calicut on the Malabar coast. Indian Hindus and Portuguese Christians shared in common a deep animosity for Islam. In 1510, Affonso de Albuquerque, the Viceroy of India, by treaty with Krishna Deva Raya, the Emperor of Vijayanagar, secured the port of Gao as a naval base for Portuguese operations in the Indian Ocean.
Albuquerque had already learned of Malacca's strategic importance to the spice trade. The very next year, in 1511, he took with him eighteen Portuguese warships from Gao and ended the Sultanate of Malacca. The loss of Malacca shattered the Islamic trade network at a blow. From so far away, though, Portugal was operating at the very limit of its power and was never quite able to rebuild the trading network it had destroyed. Ten years later, the Portuguese were greatly alarmed to see Magellan's flagship Victoria returning to Spain - westward from the Philippines.