Citadellets ursprungliga Ayyubidiska murar och torn uppfördes mellan 1176 och 1183, med hjälp av den mest aktuella tekniska kunnade som kommit att utvecklas under de 100 år man stridit mot korsfararna. Stenmurarna är 10 meter höga och 3 meter tjocka, med ännu högre vallar med invändiga korridorer, och utstickande runda torn som innebar att Citadellets garnison direkt kunde attackera alla angripare som försöker att klättra upp för borgens murar.
I Citadellet ligger även Bir Yusuf (Salah ad-Dins brunn) som försåg fästningen med sitt eget livsnödvändiga dricksvatten. Brunnen är uthuggen 87 meter rakt ned genom berget till grundvattnet, och är vid nog att innehålla en ramp för de djur som användes för att dra den maskin som lyfte upp vattnet till Citadellet. Brunnen är ett mästerverk i medeltida byggnadsteknik, och var Citadellets mest besökta turistattraktion under 1800-talet, men är tyvärr numer stängd för allmänheten.
Den andra härskande Ayyubiden, Sultan al-Adil (1200-18), ägnade sin tid vill makten åt att konsolidera det rike som grundats av hans bror, Salah ad-Din. runt om i hela Syrien och Egypten, blev alla citadellen i hans område antingen ombyggda eller tillbyggda. 1207 övervakade han personligen återuppbyggnaden av citadellet i Damaskus, medans hans son al-Kamil, som var govenör i Egypten, kom att stärka befästningarna i Kairo. Några av de torn byggts under Salah ad-Din – till exempel Burg al-Hadad (Smedens Torn), samt Burg ar-Ramlah (Sand Tornet), som kontrollerade det trånga pass mellan Citadellet och Muqattamberget — ansågs vara alltför små för att försvara borgen och kom att mer än tredubblats i storlek genom att vara inneslutas i gigantiska nya konstruktioner.
Al-Kamil byggde även flera våningar ovanpå tornen som kom att resa sig 25 meter höga med nästan 30 meter i bred. Tre av dessa stora kvadratiska torn kan fortfarande ses över Citadellets parkeringsplats.
Efter faderns död blev Al-Kamil (1218-38) den första Ayyubidiske Sultan som bodde i Citadellet. Han byggde ett palatskomplex på citadellets södra område. Även om inget av Al-Kamils palats har överlevt in i våra dagar så utgjorde denna plats centrum för den egyptiska makten ända in till 1800-talets andra hälft.
