Alhambra valmistui Alcazaba linnoituksesta, joka sijaitsi samalla paikalla 800-luvulla. Vanhan Alcazaba linnoituksen osia on vielä näkyvillä nykyisessä linnoituksessa eli Alhambrassa. Alhambra oli melkeinpä kokonaan mitätön linnoitus ennen sitä, kun Granadaan muutti paljon väkeä Cordobasta. Tämän jälkeen linnoitus toimi Nasrid-Dynastian palatsina, hovina ja monena muuna melkein 250-vuotta. Vuonna 1238 Nasrid-Dynastian ensimmäinen kuningas Mohammed I nousi kuninkaaksi. Mohammed I vahvisti linnoitusta ja hänen poikansa rakensi muurin linnoituksen ympärille. Vuonna 1333 - 1354 tuli Jusuf I. Hän aloitti rakennuttamaan palatsille loistokkaita sisätiloja sekä pihoja ja vuosina 1354 - 1391 Mohammed V viimeisteli ne. Vuonna 1300 ja siitä eteenpäi alettiin valmistaa linnoituksen tärkeimmät osat ja ne tulivat valmiiksi 1300-luvun loppupuolella ja vuonna 1400 koko linnoitus tuli valmiiksi. Kaiken tämän rakensi kristityt orjat. Vihdoin vuonna 1492 kristityt saivat vallattua takaisin Granadan. Seuraavaksi palkatut muslimirakentajat alkoivat kunnostamaan palatsia, kun hallitsijapari Ferdinand ja Isabella muuttivat sinne. Kaarle V alkoi rakentamaan sinne hänen omaa renessanssipalatsia vuonna 1526, mutta hänen palatsinsa eroaa tyyliltään muista osista, joten se on helppo erottaa.