En el año 713, con la conquista musulmana, la ciudad recibe el nombre de قلعة أسطلير (Qal`at Astalir); en el siglo IX, قلعة يحصب (Qal`at Yahsub) y, más tarde, a mitad del s. XII قلعة بني سعيد (Qal`at Banī Sa`id), esto es, "fortaleza de los Bani Sa`id o de la familia Sa`id", también, abreviadamente, القلعة Al-Qal`a, "la fortaleza", del que procede su nombre actual.
[5] En la época almohade sufrió los ataques de los bereberes norteafricanos por su rebelión manifiesta y su constitución en señorío independiente.
En esta fortaleza tuvo lugar el llamado Pacto de Alcalá, entre Alfonso X y Alhamar (1265), época en que estaba bajo control granadino.
[7] Ya en el siglo XIX, las fuerzas francesas acondicionaron y restauraron la fortaleza, construyendo un muro que iba desde el alcázar hasta la torre de la Cárcel, circundando la zona de ocupación, que incluía la iglesia Mayor abacial.
Algunos autores mantienen que pudo haberse construido originalmente en tapial, aunque durante las restauraciones realizadas no se ha detectado prueba alguna de ello.