The Sulu Genealogy clearly states that the sultanate was established after the missionary activities of a certain Karim ul-Makhdum, followed a few years by the arrival of Rajah Baguinda who was accompanied by courtiers who were presumably Muslims. Judging by their names, most of the Sulu chiefs and leaders who were to accept Rajah Baguinda as their ruler must have been Muslims. In brief, the establishment of the sultanate was based on the consent given to it by a generally Islamized people. Thus when the “tarsila” says that the first Sultan “established a religion for Sulu” and that the people accepted the new religion and declared their faith in it,” it only means that their political structure was now based on Islam and not that the first Sultan originally introduced the faith.

With some minor differences or variations, the Maguindanao tarsilas narrate how the Sharif Muhammad Kabungsuwan arrived on the shores of Mindanao with a sea-fariing people, after a long voyage from Johore. It is claimed that he was a son of the Sharif Ali Zein ul-Abidin, an Arab from Mecca (or Hadhramaut) who settled in Johore where he married a daughter (or sister, in other accounts) of the Sultan Iskandar Julkarnain. Clearly what is meant here is that the Sharif married a princess of the royal family of Johore that was descended from the dynasty founded by Iskandar Julkarnain, the first Malacca sultan. In the list of Malacca sultans, only one, the first bears his name; while in the list of the early Johore sultans, none bears it. For good chronological reasons, Muhammad Kabungsuwan could not have been a grandson of the first sultan of Malacca whose rule began around 1400. Consequently, it would have been more accurate to have stated that the Sharif Ali Zein ul-Abidin married into the Johore family that descended from Sultan Iskandar Julkarnain.