Àhmad ibn Tulun era originari de Bagdad, però de molt jove es va traslladar a Samarra. El 868 arriba al Caire com a representant del califa al-Mútazz (866-869); troba aquella capital, coneguda com al-Fustat, massa limitada per les seves tropes i funda un nou assentament, al-Qataï, donant entrada a la dinastia tulúnida, independent, de fet, de Bagdad. Al-Qataï es projecta com una gran ciutat, amb tots els seus serveis, entre els quals la mesquita, seguint un model importat de Samarra. Aquella ciutat fou arrasada el 905, la mesquita d'Ibn Tulun és un dels pocs elements que en van quedar.

A al-Fustat hi havia l'antiga mesquita d'Amr, del 641, però ja no servia a les necessitats d'Àhmad ibn Tulun. Una inscripció fragmentària original en un dels pilars del santuari porta el text de fundació i la data d'acabament, el 879. La mesquita s'havia començat tres anys abans, el 876.

Una llegenda ens fa saber que el lloc triat per a la seva construcció era el mateix on l'arca de Noè va tocar terra després del diluvi, tot i que la tradició més estesa situa aquest esdeveniment al mont Ararat. Al costat de la mesquita també es va aixecar un palau, que hi comunicava directament.

Una inscripció fragmentària damunt l'entrada de la mesquita es refereix a restauracions fetes pel visir fatimita Badr al-Jamalí, el 1177. El seu fill, Al-Àfdal Kutayfat, patrocinava un mihrab, descrit més avall.

En el període fatimita, la mesquita d'Ibn Tulun era una de les quatre en les quals el califa feia les oracions del divendres, les altres eren les d'al-Azhar, al-Hàkim i Amr.

El soldà mameluc Lajin va fer restauracions importants a la mesquita entre el 1296 i 1297. En aquella època era abandonada, però una llegenda ens explica que gràcies a haver-li proporcionat refugi quan el perseguien els seus enemics, va decidir restaurar-la. La intervenció de Lajin inclogué el minaret, la font d'ablucions nova del pati, i la cúpula de fusta damunt el mihrab principal. També va impulsar l'ensenyament de les lleis islàmiques, i fins i tot l'ensenyament de medicina. Una escola primària per a nois, per a l'ensenyament de l'Alcorà, es va afegir a la mesquita. També va patrocinar una font pública. D'aquestes estructures addicionals, tanmateix, només la font d'ablucions i la cúpula del mihrab sobreviuen.

Al segle xiii, quan la barriada havia caigut en decadència, la mesquita d'Ibn Tulun s'utilitzava com a caravanserrall per a pelegrins nord-africans en el seu camí cap a la Meca. Durant el segle xiv, un jutge va afegir-li dos minarets als extrems de la sala d'oració principal, un d'aquests es va enderrocar, ja que havia perdut estabilitat. Al segle xix s'utilitzava com a fàbrica, i més tard com a manicomi.