Historia polityczna Fatymidzi w Maghrebie thumb|200px|Wielki Meczet w Al-Mahdijji zbudowany za panowania Abd Allaha al-Mahdiego (909–934) Początki Fatymidów jako dynastii panującej na określonym terytorium wiążą się z osobą wspomnianego już powyżej Abd Allaha al-Mahdiego (909–934). Podobnie jak jego poprzednicy Abd Allah żył w Salamijji w Syrii, skąd sekretnie kierował poczynaniami sieci ismailickich misjonarzy (da'i). W roku 902 działająca bez zgody Abd Allaha grupa ismailitów pod przywództwem da’iego Zikrawajha ibn Mikrawajha zdobyła Hims i doprowadziła do powstania efemerycznego państwa w regionie rzeki Orontes. Ostatecznie jednak ta rewolta zakończyła się klęską i doprowadziła jedynie do ujawnienia tożsamości Abd Allaha, który teraz musiał uciekać przed Abbasydami. Początkowo udał się do Egiptu, później zaś do Ifrikijji, chcąc dołączyć do działającego na tym terytorium wśród Berberów Kutama da’iego Abu Abd Allaha. Te plany udaremnili jednak rządzący Ifrikijją w imieniu Abbasydów Aghlabidzi i ostatecznie Abd Allah udał się do Sidżilmasy (w pobliżu dzis. Ar-Risani).