El 713 dC/94 Hègira, amb la conquesta musulmana, la ciutat passa a denominar-se قلعة أسطلير (Qal'at Astalir), després, al segle ix, قلعة يحصب (Qal'at Yahsub) i, més endavant, a mitjans del segle xii قلعة بني سعيد (Qal'at Banī Sa'id), això és, "fortalesa dels Bani Sa'id o de la família Sa'id", també, abreviadament, القلعة Al-Qal'a, "la fortalesa", del que procedeix el seu nom actual.[1] Segons alguns autors, la talaia-castell es va erigir a principis del s. VIII,[2] pel mandatari granadí Badis Aben Habuz, com a defensa enfront de les corregudes de les hosts de Baeza, que estaven assentades en el Castillo de Locubín. Tanmateix, això va succeir, en realitat, en el s. XI, en l'època de les primeres taifes, en la qual va néixer i va morir el regne zirída berber de Granada. Se sap que abans, el 889, va ser el centre d'una de les rebel·lions muladís contra el Califat de Còrdova i que, més tard, va tenir un paper destacat en els enfrontaments entre els almoràvits i els reis de Taifes, època en què es reforcen els seus sistemes defensius i s'envolta tot l'espai habitat amb una nova muralla, aixecant-se una mesquita i un sistema complex d'accés a la part alta del turó, amb diverses portes controlades per torres albarranes.[3]

En l'època almohade va patir els atacs dels berbers nord-africans per la seva rebel·lió manifesta i la seva constitució en senyoriu independent. Abd al-Malik ben Sa'id, el seu governador i cap del clan familiar, va pagar la seva rebel·lia amb el seu empresonament en una presó al Marroc durant poc temps. Després va tornar de nou a Alcalá lliure i obedient. Després de la batalla de les Navas de Tolosa (1212), el castell va ser objecte de diversos atacs que, segons alguns autors, van suposar el seu pas a mans cristianes i musulmanes alternativament. En aquesta fortalesa va tenir lloc l'anomenat Pacte d'Alcalá, entre Alfons X i Alhamar (1265), època en què estava sota control granadí.[4] Entre mitjans del segle xiii i el XIV, es va organitzar un sistema defensiu de talaies-vigia que controlava la línia fronterera fixada en el Pacte de Jaén.

El 1340, Alfons XI va assetjar la ciutat, que va capitular vençuda manca d'abastiment alimentari el 1341, passant definitivament a ser un dels principals llocs fronterers del Regne de Castella enfront del Regne nassarita de Granada. Fins a la caiguda de Granada, el castell de la Mota va disposar de nombroses dotacions de Castella, realitzant-se algunes obres, com l'aixecament de l'anomenada "Torre Nova". No obstant això, una vegada conquistada Granada, la fortalesa es va anar abandonant gradualment i tot el sistema defensiu "va anar caient en l'estat d'incúria que arribaria al segle xviii, coincidint amb el despoblament de l'alcassaba pels ravals del pla".[5]

 La ciutat va començar a traslladar-se des de la fortalesa al pla al segle xvii

Ja al segle xix, les forces franceses van condicionar i van restaurar la fortalesa, construint un mur que anava des de l'alcàsser fins a la Torre de la Presó, circumdant la zona d'ocupació, que incloïa l'Església Major abacial. El 1812, en acabar la Guerra del Francès, l'Església Major, utilitzada com a magatzem, va ser incendiada, la qual cosa va provocar el desplomament de part de la volta, i es va provocar l'explosió del polvorí que albergava la Torre de la Presó, destruint gran part dels seus murs. La deterioració de la fortalesa es va agreujar per l'impacte d'artilleria en la guerra civil espanyola, i no es restauraria de nou fins temps recents.