The royal house were of noble origin, holding the hereditary position of bendahara (the highest rank in Malay nobility) in the courts of Singapura, Malacca and Old Johor since at least from the end of the 13th century.

[1] The ascendancy of the family as a royal house began in the late 17th century, when the last ruler of Johor from the Malacca dynasty, Mahmud Shah II died without a male heir.

[5] During the reign of Mahmud Shah III, the great-grandson of Abdul Jalil IV, the Sultan's power was effectively reduced to the capital in Daik, Lingga.

While the rest of the empire was administered by three powerful ministers, the Bendahara in Pahang, the Temenggong in Johor and Singapore, and the Yamtuan Muda in Riau.

Meanwhile, in Johor, Hussein Shah and his son Ali were reduced to puppet monarchs and played a minimal role in the administrative affairs of the state, which gradually came under the charge of the Temenggong and the British.

[9] The genealogy of Bendahara family is obtained through several sources, but the most important is the Malay Annals that provide the extensive account from the era of Singapura up until Johor.

The ancestry of Tun Habib Abdul Majid became highly controversial, considering his eminent role as the great ancestor of the ruling dynasties of Johor, Pahang and Terengganu.

According to this version, the current ruling house of Bendahara are the patrilineal descendants of the Ba'Alawi Sada, an offshoot of the Banu Hashim tribe hailing from Hadhramaut, in what is now Yemen.

In the late 16th century, a descendant of the Banu Hashim clan, Sayyid Idrus, was among the earliest Arab settlers that served as religious leaders in Aceh.