Pochi anni dopo aver dichiarato estinta la dinastia fatimide, Saladino decise di costruire delle mura che circondassero sia Il Cairo sia al-Fustat. Secondo alcune fonti, Saladino disse: «Con un muro farò delle due città di Cairo e Fustat un tutto unico, in modo che un esercito possa difenderle entrambe, e credo sia bene circondarle con un muro che vada dalle rive del Nilo alle rive del Nilo». La cittadella sarebbe stata al centro delle mura. Fu costruita su un promontorio ai piedi della collina al-Muqaṭṭam, in un sito difficile da attaccare.[1] Il sito, parte della collina del Muqaṭṭam, vicina al centro del Cairo, era un tempo famoso per la fresca brezza e per la superba visione sulla città. La cittadella smise di essere la sede del governo quando Isma'il Pascià si trasferì nel nuovo Palazzo 'Abidin, nel quartiere di Ismāʿīliyya negli anni settanta dell'Ottocento.

Mentre la Cittadella venne completata nel 1183-1184, le mura immaginate da Saladino erano ancora in costruzione nel 1238, molto tempo dopo la sua morte.

Per l'approvvigionamento idrico alla Cittadella, Saladino costruì il "Pozzo di Giuseppe", che può ancora essere visto oggi. Il pozzo è noto anche come il "Pozzo della spirale", perché il suo ingresso era costituito da 300 gradini che si snodavano intorno alla parete interna. L'acqua sollevata dal pozzo alla superficie veniva convogliata alla Cittadella tramite una serie di acquedotti. Durante il regno del sultano mamelucco al-Nasir Muhammad, il Pozzo di Giuseppe non riusciva a fornire acqua a sufficienza ai numerosi animali e agli esseri umani che vivevano nella Cittadella. Per aumentare il volume di acqua, al-Nasir Muhammad costruì quindi un sistema costituito da una serie di norie che sollevavano l'acqua del Nilo. Questa veniva poi incanalata lungo le mura e condotta alla Cittadella mediante tubazioni costruite da Saladino. In seguito altri sultani Mamelucchi apportarono delle migliorie.

Il contributo più notevole realizzato da al-Nasir Muhammad fu la costruzione della moschea di al-Nāṣir. Nel 1318, al-Nasir Muhammad ricostruì la struttura originale, che risaliva al tempo degli Ayyubidi, trasformandola in una moschea alla quale diede il suo nome. La struttura ricevette ulteriori aggiunte nel 1335. Altri contributi alla Cittadella durante il regno di al-Nasir Muhammad comprendono la recinzione meridionale (il recinto nord era stato completato da Saladino) e la zona residenziale, che comprendeva lo spazio per l'harem e il cortile. Prima dei lavori fatti eseguire da al-Nasir Muhammad, i due Baybars costruirono il Palazzo di Giustizia e la "Casa d'Oro".[1]

La Cittadella è spesso chiamata erroneamente Cittadella di Muhammad Ali (in arabo قلعة محمد علي‎?, Qalʿat Muḥammad ʿAlī), poiché in essa si trova la Moschea di Muhammad ʿAli Pascià, costruita fra il 1828 e il 1848, sulla sommità.[2] Questa moschea ottomana venne costruita in memoria di Ṭūsūn Pascià, figlio maggiore adottato di Muhammad Ali, che morì nel 1816. Tuttavia, essa rappresenta anche gli sforzi realizzati da Muhammad Ali nel voler cancellare i simboli della dinastia mamelucca che aveva sconfitto nel 1805. Un cambiamento evidente realizzato da Muhammad Ali è visibile nelle recinzioni nord e sud della cittadella. Durante il periodo mamelucco il settore sud delle mura era la zona residenziale, mentre Muhammad Ali optò per le mura nord come sede della residenza reale quando prese il potere. Egli aprì poi le mura sud al pubblico affermando così la sua posizione di leader del nuovo regime.[3].

La moschea, con la sua grande cupola di architettura prettamente ottomana, sovrasta la Cittadella fino ai nostri giorni. Per far posto alla costruzione della moschea Muhammed Ali fece abbattere diversi palazzi recenti fatti costruire dai mamelucchi, e fra questi la loro residenza, realizzando la più grande struttura architettonica costruita nel XIX secolo. Il posizionamento della moschea sui luoghi in cui i Mamelucchi avevano regnato, fu un evidente sforzo di cancellare la memoria degli antichi governanti e stabilire l'importanza della nuova dinastia. La nuova moschea sostituì la moschea di al-Nasir Muhammad come la moschea ufficiale di Stato.[2]

Nella cittadella esistono altre due moschee, quella di al-Nasir Muhammad,[4] ipostila del XIII/XIX secolo, una moschea della dinastia Bahri, e quella di Suleyman Pascià del XVI secolo, la prima moschea costruita in stile ottomano sulla Cittadella.

Altro edificio notevole è Qasr al-Jawhara (Il Palazzo dei Gioielli), dove hanno sede il Museo nazionale militare e il Museo della Polizia.