Kalaja e Gjirokastrës si histori e lidhur me qytetin e Gjirokastrës, përmendet për herë të parë si qytet dhe kështjellë në vitin 1336.
Në këto vite, ajo ishte qendra e feudalëve shqiptarë Zenevisë. Më vonë, gjatë sundimit të Gjin Bue Shpatës, ajo u përfshi në Despotatin e Epirit. E megjithatë historianë të ndryshëm mendojnë se ekzistenca e kalasë së gurtë është më e hershme. Sipas tyre, kalaja ka pas dy faza ndërtimi, të cilat lidhen me periudhën para dhe pas Pashallëkut të Janinës dhe fortesave të Ali Pashë Tepelenës. Nga Kalaja mesjetare, ajo e para pushtimit të Ali Pashës, ruhen vetëm pak gjurmë pasi muret janë veshur deri në lartësi nga ndërtimet e reja.
Ndërsa, kullat pjesërisht janë rrënuar dhe ripërshtatur.
Sipas kronikanit turk, Çelebiu, i cili vizitoi qytetin më 1672: “ Kalaja ishte ndërtuar në kohë të moçme. Krejt prej guri të gdhendur. Në mes të kalasë ndodhej një rrugë e gjerë me drejtim lindje-perëndim, në të dy anët e së cilës ndodheshin 200 shtëpi. Ajo kishte dy porta hekuri me nga tri palë dyer dhe një hendek 100 hapa të gjatë dhe 200 hapa të gjerë midis namasgjahut dhe fortesës. Ndërsa të tri anët e tjera nuk kishin nevojë për hendek pasi janë përrenj natyrorë”.
Në vitin 1417, Kalaja u pushtua nga turqit pas një rrethimi të gjatë.
Me kalimin e viteve, ajo filloi të luajë gradualisht rolin e një kështjelle për qëndrimin e sunduesit dhe garnizonit të qytetit. Në vitin 1812, Kalaja e Gjirokastrës u pushtua nga Ali Pashë Tepelena, i cili filloi rindërtimin e saj. Rindërtimi i kalasë, i një saraji dhe i disa godinave anekse, u bë me një ngutësi aq të madhe sa të gjitha punimet u kryen brenda një viti e gjysmë.
Kalaja përmbante përveç barakave për vendosjen e një garnizoni prej 5 mijë ushtarësh, magazina të shumta nëntokësore që ishin llogaritur mirë për sigurimin e municioneve dhe ushqimeve të nevojshme. Kronikat e kohës përmendin se vetëm për ndërtimin e vendqëndrimit të Ali Pashës, një kullë pranë këndit juglindor, punuan 1500 vetë. Me rënien e Pashallëkut të Janinës, Kalaja do të humbiste shkëlqimin e saj.
Në vitet e luftës së Parë dhe të Dytë Botërore, ajo do të shërbente si vendstrehim për banorët e qytetit për tu mbrojtur nga bombardimet e ajrore.
