Alcazaba, cietoksnis, ir viena no vecākajām Alhambras daļām, kā tas ir Vermilion torņu (Torres Bermejas) gadījumā. Tiek uzskatīts, ka pirms tā tika uzcelta un pirms musulmaņi ieradās Granadā, tajā pašā apgabalā jau bija vairākas konstrukcijas. Pirmā vēsturiskā atsauce uz Alcazaba esamību ir datēta ar 9. gadsimtu, un tiek uzskatīts, ka to uzcēla Sawwar ben Hamdun cīņu laikā starp musulmaņiem un muwalladins [kristieši, kuri pārveidoja par islāmu un dzīvoja starp musulmaņiem].
Pašreizējo kompleksu uzcēla Mohammed I, kurš uzbūvēja vaļņus ap iepriekšējo pili, aizsargus un trīs jaunus torņus: šķelto torni (Torre Quebrada), Keep (Torre del Homenaje) un pulksteņu torni (Torre de la Vela). Tā rezultātā Alcazaba kļuva par īstu cietoksni, kur karalis izveidoja karalisko dzīvesvietu. Viņa dēlam Mohammedam II bija arī dzīvesvieta Alcazaba, līdz pilis tika pabeigtas. No tā brīža Alcazaba tika izmantota tikai kā cietoksnis militāriem mērķiem.
Kad kristieši paņēma pilsētu, viņi veica daudzus darbus, lai labotu Alcazaba. Dažādos vēstures brīžos ilgu laiku to izmantoja kā valsts cietumu pat Francijas okupācijas laikā.
Tāpat kā Alhambra, Alcazaba tika pamesta un netika aprūpēta ilgu laiku, un tikai 19. gadsimta beigās un 20. gadsimta sākumā tika uzsākti atjaunošanas, izpētes un santehnikas darbi.