Badis ibn Habús, emir de Granada, ordenà construir l'alcassaba entre els anys 1057 i 1063,[1] utilitzant per al seu embelliment els marbres i estàtues del teatre romà adjacent.

Els almoràvits hi irromperen el 1092 i els almohades el 1153.[2] Posteriorment, el 1279, és rendida la ciutat a Muhàmmad II al-Faqih i passa a formar part del Regne nassarita.[3]

L'alcassaba participà en la conquesta de Màlaga per Ferran el Catòlic, que després de vèncer i conquerir el Zagal a Vélez,[4] assetjà i conquerí Màlaga.[5] El 19 d'agost del 1487 entraren a la ciutat els reis Catòlics, que van tomar possessió de la ciutat, rendida per fam després del llarg setge.[5] Van alçar la creu i el penó de Castella en la torre de l'Homenatge. El rei Ferran donà a Màlaga la imatge de la Verge de la Victòria, d'origen alemany, donada per l'emperador Maximilià I al monarca, que des de llavors és la patrona de la ciutat.

Posteriorment, tot el recinte va viure un procés d'abandonament i saqueig. Els murs exteriors foren utilitzats per a la creació de les cases del barri de la Coracha. No fou fins a les primeres dècades del segle xx quan es comença a rehabilitar l'edifici.