The sultanates of Sulu and Borneo were well established political entity in the Malay world during the late 15th and 16th century. The Arabs, who had settled in Malacca in 1400, did not extended political control over the two sultanates other than spreading the teaching of Islam. The Chinese did the same who frequented the areas held by the two sultanates to trade with the natives.
The sultanate of Sulu was founded in 1380, nearly one and a half century before the arrival of the Spaniards in the Philippines. The sultanate possessed an efficient political organization, extending its influence in Zamboanga, Basilan, Palawan, aside from the Sulu archipelago. During its supremacy, the sultanate extended its control as far as the Visayas and Luzon until controlled by the Spanish conquistadores in the Philippines. For many years to come, as the colonial government consolidated it territory, the sultanate was to remain a problem by the Spanish and American colonial government (viewed as pirates and buccaneers).
The Sultanate of Brunei, on the other hand, was founded in the 15th century. For a brief period, it became a tributary of the Majapahit Empire. Before the British entry in to the region, the sultanate exercise nominal control over the whole northwestern and eastern coast of the island.
Related by its common Malay origin, the two sultanates were bounded together by religious ties with the spread of Islam in the Malay world. Trade between their respective subjects served to reinforce this relationship even more.