Het sultanaat ontstond in 1636, in de periode dat de Ottomanen zich terugtrokken uit het huidige Jemen en het gebied uiteenviel in diverse staten, waaronder Bayda, die feitelijk onafhankelijk waren van zowel de Ottomanen als Jemen. In de tweede helft van de 19e eeuw sloten veel staten protectieverdragen met de Britten (het Protectoraat Aden), maar tot een protectieverdrag voor Bayda kwam het niet. Tijdens de Eerste Wereldoorlog lukte het Bayda om een Ottomaanse verovering te voorkomen. Bayda bleef onafhankelijk tot 1930, toen het gebied veroverd werd door het Koninkrijk Jemen.
