The city was founded on the Gabal Yashkhur, a hill to the northeast of the existing settlements that was said to have been the landing point for Noah's Ark after the Deluge, according to a local legend.

Likewise, certain areas of al-Qata'i were allocated to officers, civil servants, specific military corps, Greeks, guards, policemen, camel drivers, and slaves.

Ibn Tulun's palace, the Dar al-Imara ("House of the Emir") was built adjacent to the mosque and a private door allowed the governor direct access to the pulpit, or minbar.

Ibn Tulun also commissioned the construction of an aqueduct to bring water to the existing town, and a maristan (hospital), the first such public institution in Egypt, founded in 873.

In 905, Egypt was reoccupied by the Abbasids, and, in retaliation for the Tulunids long military campaigns against the caliphate, the city was plundered and razed, leaving only the mosque standing.