Philippine history Teodoro Agoncillo claims that Buranuns, the natives of Sulu, have had historical experience with the Orang Dampuan or the "People of Champa"
In another book, it is claimed that the Orang Dampuans were vassals of the Sri Vijaya Empire who established trading colony with the Buranuns of Sulu, eventually settled in Taguima (now Basilan) and become the Yakan ancestors. 
"Later, after the island had come under the dominion of Sri-Vishaya, Champa ships came again to Sulu. That they continued to trade there is substantiated by the claim in an early Sulu manuscript that in the century before the arrival of the Spaniards from four hundred to five hundred junks arrived annually from Cambodia, Champa and China, with which Sulu principally traded. At that time the island is said to have been very densely populated and to have been one of the great trade centers of the Archipelago." 
Sulu as a Sultanate was established circa 15th century at the twilight of the Madjapahit Empire, the latter have ruled the Nusantara since the 13th century or for more than two hundred years. Where and how was Sulu during these periods in the history of the Malay World?
The Majapahit was Buddhist. In the Kretagama Nagara, King Sri Rajasanagara is considered as an incarnation of Shiva.
In Canto 13 and 14 are names of areas that were under the sway of the Majapahit . "Solot" is considered Sulu [ref]. Reference:
 Kretagama Nagara http://kelembagaan.pnri.go.id/Digital_Docs/homepage_folders/activities/highlight/naskah_nagara_kretagama/isi.htm
New Stone Age (c.5,900 - c. 5,220 BC)
"Then on the island of Sanga-Sanga, in the southern end of the Sulu Archipelago, a cave was found at the inner edge of a small cove. The cave was used by human habitation between 5,900 and 5,220 years before the birth of Christ. On the cave floor were debitage of living in a marine enviornment: tons of shells broken open; Palaeolithic types of tool knapped from obsidian, volcanic stuff, andesite, cryptocrystalline quartz and silicified wood; tools made from bone; and an adze made from the thick hinge of the Tridacna gisas, the giant clam." "The oldest in the region of Southeast Asia is from the 13th millennium B.C., and the Sanga-Sanga cave pottery was among the first pottery to appear in the Philippines. It is the first true sign of an attempt by humans in this part of the world to consciously include, on a wholly pragmatic object, an imprint of what lifts humans above the beasts. It is highly pro…