The first evidence for the opening of the sea route between India and China comes from the report of a Chinese traveller, Fa Hsien, in 413 AD that he had taken a ship from Sri Lanka directly to China. The beginning of the T'ang dynasty in 618 AD brought renewed stability to China and greatly stimulated the trade and traffic on the India-China sea route through the Indo-Malayan archipelago. For the kingdoms along the Sunda and Malacca Straits, their goal was no longer merely to participate in the China-India trade but to control it as it passed by their territories.
For more than 600 years, the Buddhist kingdom of Sri Vijaya was the strongest of the Straits kingdoms. Sri Vijaya was located at Palembang in southern Sumatra facing out on the Sunda Straits. The kingdom is first recorded in 650 AD as having conquered the west Java kingdom of Taruma. A passing Chinese monk in 671, I-Tsing, comments favourably on Sri Vijaya as a fine centre of Buddhist learning. The kingdom was in regular communication and exchange with Nalanda; the centre of Buddhist scholarship in the Ganges delta of northern India.
By 686, Sri Vijaya had asserted its hegemony over the Sunda Straits and the adjacent Javanese kingdoms. A century later, in 775, it had similarly dominated the Straits of Malacca and commanded tribute from all the kingdoms along its shores. Attaining monopoly control over the trade through the Straits and then keeping it demands a special ruthlessness in suppressing rivals and discouraging interlopers. Sri Vijaya was equal to the task.
While Sri Vijaya was establishing its predominance, three generations of Sailendra kings in central Java, between 770 and 825, built the magnificent Buddhist temple complex of Borobudur.
By the late 10th century, the Javanese kingdoms were mounting a serious challenge to Sri Vijaya's hegemony; so much so that in 992 it sent a mission to China seeking protection from its enemies. No doubt the Chinese appreciated the importance of order and stability for the security of traffic through the Straits. In the 11th century, Sri Vijaya's Malayan tributaries sought help from India in throwing off its dominance. The Indian Chola states attacked Sri Vijaya in 1017, 1025 and again 1068. By 1200, Sri Vijaya had lost control over several of its principal tributaries on the Malay Peninsula and Sumatra.
From about this time in the Philippines comes the historical legend of the Ten Datus from Sabah who settled in the Visayas sometime around 1212. The Ten Datus were clearly escaping from an overbearing presence on Borneo rather than appropriating new domains in the name of their sovereign. That the legend calls them "datus", not Rajas or Sultans, indicates they were Austronesian chiefs and not the heads of politically organized states.
With Sri Vijaya under attack and weakened, the rival Javanese kindoms of Kediri and Singhasari grew in power. Finally in 1290, Singhasari drove Sri Vijaya out of Java altogether. The rising power of Singhasari attracted the attention of China's Mongol Emperor Kublai Khan who in 1289 had demanded a payment of tribute. Kublai Khan's ambassadors returned to China without their noses. A Mongol fleet arrived in the Java Sea in 1293.