The Sultanate of Bulungan was a princely state of Indonesia located in the existing Bulungan Regency in the North Kalimantan province of Indonesia in the east of the island of Borneo. With its territory spanning throughout the eastern shores of North Kalimantan and Tawau, Malaysia.
The Sultanate was founded by a Kayan group, the Uma Apan, who originated from the interior region of Apo Kayan (Kayan Highland Plateau), before settling near the coast in the 17th century. Around 1650, a princess of the group married a man from Brunei. This marriage founded a Hindu lineage who settled in the region of today’s Tanjung Selor. Around 1750, this dynasty converted to Islam. Its rulers took the title of Sultan and were recognised as vassals of the sultan of Berau, the latter acknowledging himself a vassal of the kingdom of Kutai.
In 1850, the Dutch, who had conquered Berau in 1834 and imposed their sovereignty upon Kutai in 1848, signed with the Sultan of Bulungan a Politiek Contract. The Dutch intervened in the region to combat piracy and the trafficking in slaves.
Until 1860, Bulungan was a subject of the Tausug of the Sultanate of Sulu. During this period, vessels began travelling to Sulu, Tarakan, and thence into the interior of Bulungan, to trade directly with Tidung. This influence ended in 1878 with the signing of a treaty between the English and Spanish partitioning Sulu.