The materials for the history of Sulu are meagre, and great doubt seems to exist in some periods of it.  That which I have been able to gather is as follows: 

[History.] The island of Sulu is generally believed to have been originally inhabited by Papuans, some of whom, as I have already stated, are still supposed to inhabit the mountainous part.  The first intercourse had with them was by the Chinese, who went there in search of pearls.  The Orang Dampuwans were the first of the Malays to form settlements on the islands; but after building towns, and making other improvements, they abandoned the islands, in consequence, it is said, of the inhabitants being a perfidious race, having previously to their departure destroyed as many of the natives as they could.

The fame of the submarine riches of this archipelago reached Banjar or Borneo, the people of which were induced to resort there, and finding it to equal their expectation, they sent a large colony, and made endeavors to win over the inhabitants, and obtain thereby the possession of their rich isle.  In order to confirm the alliance, a female of Banjarmassing, of great beauty, was sent, and married to the principal chief; and from this alliance the sovereigns of Sulu claim their descent.  The treaty of marriage made Sulu tributary to the Banjarmassing empire.

After the Banjars had thus obtained possession of the archipelago, the trade in its products attracted settlers from the surrounding islands, who soon contrived to displace the aborigines, and drive them to the inaccessible mountains for protection.

When the Chinese took possession of the northern parts of Borneo, under the Emperor Songtiping, about the year 1375, the daughter of that prince was married to a celebrated Arabian chief named Sheriff Alli, who visited the shores of Borneo in quest of commerce.  The descendants of this marriage extended their conquests not only over the Sulu Archipelago, but over the whole of the Philippines, and rendered the former tributary to Borneo.  In three reigns after this event, the sultan of Borneo proper married the daughter of a Sulu chief, and from this union came Mirhome Bongsu, who succeeding to the throne while yet a minor, his uncle acted as regent.  Sulu now wished to throw off the yoke of Borneo, and through the intrigues of the regent succeeded in doing so, as well as in retaining possession of the eastern side of Borneo, from Maludu Bay on the north, to Tulusyan on the south, which has ever since been a part of the Sulu territory.

This event took place before Islamism became the prevailing religion; but which form of idolatry, the Sulus pretend, is not now known.  It is, however, believed the people on the coasts were Buddhists, while those of the interior were Pagans.

The first sultan of Sulu was Kamaludin, and during his reign one Sayed Alli, a merchant, arrived at Sulu from Mecca.  He was a sherif, and soon converted one-half of the islanders to his own faith.  He was elected sultan on the death of Kamaludin, and reigned seven years, in the course of which he became celebrated throughout the archipelago.  Dying at Sulu, a tomb was erected to him there, and the island came to be looked upon by the faithful as the Mecca of the East, and continued to be resorted to as a pilgrimage until the arrival of the Spaniards.