Po podboju Egiptu wódz działający w imieniu Fatymidów, mających wówczas bazę na terenie Tunezji, Dżawhar as-Sikilli, założył 8 sierpnia 969 nowe miasto, nazwane Al-Kahira od planety Mars. W 971 kalif fatymidzki Al-Mu’izz przeniósł swój dwór z Al-Mansurijji w Tunezji właśnie do Al-Kahiry, czyli Kairu. Mimo to Al-Fustat pozostał faktycznie głównym ośrodkiem Egiptu pod względem administracyjnym i gospodarczym. Al-Fustat stale się rozrastał. W 987 geograf Ibn Hawkal zanotował, że jest równy ⅓ Bagdadu – stolicy kalifatu, w 1168 liczba jego mieszkańców doszła do 200 tysięcy. Na jego obszarze pobudowano rozległe budynki mieszkalne, niektóre dochodzące do 7 kondygnacji, według relacji Persa, Nasira Chusrawa, z początku XI w. nawet 14 pięter, z ogrodami na dachu, nawadnianymi przez koła wodne, napędzane przez zwierzęta pociągowe. Wykopaliska przeprowadzone na terenie miasta odsłoniły przedmioty pochodzące aż z Wietnamu i Chin.