Egipto fue gobernado desde esta fortaleza desde el siglo XI hasta el XIX. Fue construida por Saladino, que expulsó al último califa fatimí en 1171, pero se amplió y reformó varias veces.

En la época de Saladino, en la ciudadela de El Cairo se hallaban los palacios reales, los cuarteles del ejército y las oficinas del gobierno. Desde 1250 los antiguos gobernantes mamelucos sustituyeron muchos edificios por estructuras con un estilo majestuoso, pero estas a su vez también fueron derruidas, exceptuando la mezquita de An-Nasir Muhamad, que se terminó en 1335.

El harén, con sus pabellones, sus jardines y una población de 1.200 personas, estaba ubicado en el lugar que ahora ocupa la mezquita de Muhamad Ali. En 1400, alrededor de 6.000 jóvenes eran esclavos en el palacio del sultán.

Las mezquitas, las puertas y las torres de homenaje fueron añadidas después de 1517, cuando Egipto era una provincia del Imperio otomano que gobernaba pachás turcos. Entre estas edificaciones está la tome Burg al-Muqatam, que se alza 25 m por encima de la entrada este.

Hacia 1650 la ciudadela se había convertido en un barrio residencial con calles, casas privadas y tiendas, mercados y baños públicos. Las tropas de Napoleón la ocuparon después de invadir Egipto en 1798, y luego pasó a manos de los británicos desde 1882 hasta su salida en 1947.

El pachá Muhamad All fue nombrado virrey de Egipto por el emperador otomano en 1805, e instauró una dinastía que gobernó hasta 1953.

Fue un gran modernizador -su nuevo palacio en la ciudadela estaba iluminado con gas -renovó El Cairo construyendo nuevas calles y sustituyendo los edificios viejos entre ellos la colosal y recargada mezquita, que se terminó en 1848. All fue enterrado en la mezquita.

Actualmente, el complejo alberga el Museo Nacional de Policía y el Museo Militar Egipcio.