The mosque formed part of the new suburb of al-Qata'ic which ibn Tulun added onto the two towns of Fustat and al-'Askar which were later incorporated into the city of Cairo. Ahmad ibn Tulun was born in Iraq and brought up at the caliph's court in Samarra and the new city of al-Qata'ic bore some resemblance to Samarra.
The mosque was begun in 876 and completed in 879. The building consists of a large rectangular enclosure with a central courtyard measuring 92 m square. Arcades two-aisles deep are ranged around three sides of the courtyard whilst on the qibla side (south-east) there are five rows of arcades. The central building is enclosed by an outer enclosure, or ziyada, on the three sides adjoining the qibla. Almost directly opposite the central mihrab is a minaret consisting of a square tower with a spiral section on the top. Access to the top of minaret is by an external staircase. At the top there is a two-storey octagonal kiosk. Whilst the octagonal kiosk and the windows on the side of the square shape appear to be of a later (thirteenth century) date there is some debate about whether the minaret is an original ninth-century structure or a later copy.
Due to its good state of preservation the Ibn Tulun Mosque provides an excellent example of ninth-century decoration and structural techniques. The most notable feature of the outer walls is the decorative openwork crenellations which resemble paper cut-outs. The courtyard facades consist of slightly pointed arches resting on rectangular piers with engaged colonettes, which is an unusual arrangement for Cairo where marble columns were usually used. Between the arches are rectangular arched niches also with engaged colonettes. Either side of each niche is a sunken rosette divided into eight lobes. A band of similar rosettes forms a cornice running around the four faces of the courtyard. Probably the most remarkable feature of the decoration is the carved stucco work which decorates the interior of the mosque. The best examples are in the soffits of the arches of the sanctuary where geometric interlace patterns are filled with stylized leaf ornament similar to Samarra stucco style B. The edges of the arches and the capitals are decorated with stucco resembling Samarra style A.
Many elements of the Ibn Tulun Mosque recall the architecture of Samarra, in particular the ziyadas, the rectangular piers and the stucco work. The minaret recalls the spiral minarets of the Great Mosque and the Abu Dulaf Mosque both because of the spiral shapes used and the positioning of the ziyada opposite the mihrab.