Kairska Al-Kata'i Meczet był pomyślany początkowo jako centralny punkt założonej przez Tulunidów stolicy, o nazwie Al-Kata'i (ob. dzielnica Kairu), do której przenieśli się z założonego przez Amra Ibn al-Asa Al-Fustat. Pierwotnie meczet przylegał do pałacu Ibn Tuluna, z którego można się było dostać bezpośrednio do sali modlitewnej przez drzwi umieszczone w pobliżu minbaru. Po zniszczeniu osiedla Al-Kata'i na początku X w. meczet był jedynym ocalałym obiektem.

Gruntowne remonty meczetu Meczet kilkakrotnie poddawano generalnemu remontowi. Po raz pierwszy w 1177, na rozkaz wezyra fatymidzkiego Badra al-Dżamali, co zostało upamiętnione inskrypcją na jednej z płyt meczetu, zawierającą szyicką wersję szahady, z dodanymi pod koniec słowami: „(Wierzę, że) [...] a Ali jest namiestnikiem Boga”. Po raz ostatni meczet został odremontowany w 2004 z inicjatywy Najwyższej Rady Egiptu ds. Starożytności.

Architektura thumb|200px|right|Studnia do ablucji sabil, wybudowana przez sułtana mameluckiego Ladżina (1296 - 1299);