The Rustamid (or Rustumid, Rostemid) dynasty of Ibadi Kharijite imams ruled the central Maghreb for a century and a half from their capital Tahert , until destroyed by the Fatimids. Their state's extent is not entirely clear, but it stretched as far east as Jabal Nafusa in Libya.

The Ibadi Kharijites reached north Africa by 719, when the missionary Salma ibn Sa'd was sent from the Ibadi jama'a of Basra to Kairouan. By 740, their efforts had converted the major Berber tribes of Huwwara around Tripoli, Nafusa in Jabal Nafusa , and Zenata in western Tripolitania. In 757 (140 AH), a group of four Basra-educated missionaries (including Abd ar-Rahman ibn Rustam ) proclaimed an Ibadi imamate, starting an abortive state led by Abul-Khattab Abdul-A'la ibn as-Samh which lasted until the Abbasids suppressed it in 761, and Abul-Khattab Abdul-A'la ibn as-Samh was killed. On his death, the Tripolitanian Ibadis elected Abul-Hatim al-Malzuzi as imam; he was killed in 772, after launching a second unsuccessful revolt in 768. After this, the center of power shifted to Algeria, and Abd ar-Rahman ibn Rustam , a Tunisian-born convert to Kharijism of Persian origins already mentioned as one of the four founders of this imamate, was elected imam; after this, the post remained in his family, a practice which the Ibadis justified by noting that he came from no tribe, and thus his family had no bias towards any of the tribes of which the state was formed.

The new imamate was centered on the newly built capital of Tahert ; several Ibadi tribes displaced from Tunisia and Tripolitania settled there, and strong fortifications were built. It became a major stop on the newly developing trade routes with sub-Saharan Africa and the Middle East. It is described by visitors, such as the Sunni Ibn as-Saghir , as notably multi-religious, with a significant and loyal Christian minority and a substantial number of Sunnis and Jews, and open religious debate was encouraged. Ibn as-Saghir also describes the imam as notably ascetic, repairing his own house and refusing gifts; the citizens sharply criticized him if they considered him derelict in his duty. Religious ethics were strictly enforced by law.

The Rustamids fought the Aghlabids in 812, but otherwise reached a modus vivendi; this displeased the Ibadi tribes on the Aghlabid border, who launched a few rebellions.

After Abdul-Wahhab, the Rustamids grew militarily weak; they were easily conquered by the Fatimids in 909, upon which many Ibadis - including the last imam - fled to the Sedrata tribe of Ouargla, whence they would ultimately emigrate to Oued Mzab .

Rustamid Imams

• Abd ar-Rahman ibn Rustam ibn Bahram (776-784)
• Abd al-Wahhab ibn Abd ar-Rahman (784-832)
• Aflah ibn Abd al-Wahhab (832-871)
• Abu Bakr ibn Aflah (871)
• Muhammad Abul-Yaqzan ibn Aflah (871-894)
• Yusuf Abu Hatim ibn Muhammad Abil-Yaqzan (894-897)
• Yaqub ibn Aflah (897-901)
• Yusuf Abu Hatim ibn Muhammad Abil-Yaqzan, again (901-906)
• Yaqzan ibn Muhammad Abil-Yaqzan (906-909)