Ahmad ibn Tulun was sent from Samarra as governor of Egypt for the Abbasid caliphate and made the province effectively independent. He built a new administrative city, al-Qata'i, and this was its congregational mosque, completed between 876 and 879.
Almost all of al-Qata'i was destroyed afterwards. The mosque is essentially the only thing left of it, which makes it the oldest mosque in Cairo still standing substantially as it was built. Older structures survive in the city — the Nilometer on Rawda Island, the Roman walls of the Fortress of Babylon — but no other mosque of this age has come down so nearly intact.
It is built of fired brick covered in carved stucco, not the cut stone that later Cairo used, and it is fronted on three sides by an outer enclosure — the ziyada — that holds the streets back from the mosque walls. There is no ziyada behind the qibla wall, which originally abutted Ibn Tulun's own palace, the Dar al-Imara. The domed fountain in the centre of the courtyard is a Mamluk replacement, added when Sultan Lajin restored the whole building at the end of the thirteenth century.
The arcades are carried on brick piers rather than on columns salvaged from older buildings, and the arches they support are pointed — more than two centuries before the pointed arch became standard in Gothic Europe. A carved wooden frieze of Qur'anic text ran below the arcade ceilings.
By the late thirteenth century the mosque had fallen out of regular use. Sultan Lajin, who the chroniclers say hid in the derelict building while a fugitive, restored it in 1296, and the minaret now standing is usually assigned to that campaign rather than to Ibn Tulun's own builders. Systematic repair came only with the Comité de Conservation des Monuments de l'Art Arabe, set up in 1881.