The current Alcazaba is the result of four stages: the Andalusian period, from the 10th to the 15th century; the Reconquista at the end of the 15th century; the 18th century; the abandonment of its military structure and deterioration, from the 19th century to the beginning of the 20th century; and its recovery as a Historic-Artistic Monument from the 1930s to the present.

Muslim historians say Badis ben Habs, the Berber monarch of Taifa, ordered the Alcazaba to be erected with marble, columns, and statues from the nearby Roman theater. Other researchers disagree since there is evidence that the Phoenician walled enclosure was renovated, not built. Before Ben Habs, the Hammudid dynasty, the final caliphs of Córdoba and monarchs of the Taifa of Málaga, used the Alcazaba as a splendid palace.

The Almoravids and Almohads invaded it in 1092 and 1146. In 1279, Muhammad II Ben al-Ahmar ceded it to the Nasrid Kingdom of Granada.

Ferdinand the Catholic assaulted the castle of Hamet el-Zegr and his golems in Malaga after conquering El Zagal in Velez. The Alcazaba was a Nasrid fortress at this time. The siege began on May 5, 1487, with 3,000 gomeres and 8,000 armed men in the Nasrid army. Ali Dordux gave up the Alcazaba on August 18 after becoming a Mudejar, while El Zegr and Ali Derbal led the Alcazar of Gibralfaro for two more days until succumbing to starvation and thirst. The Catholic Monarchs arrived on August 19 and raised the cross and Castilian flag on the Alcazaba's keep. King Ferdinand gave Malaga a carving of the Virgin of Victory, the city's patron saint. The Spanish monarch received the carving from Holy Roman Emperor Maximilian I.

The earthquake of 1680 and the Nine Years' War bombardment by nine French ships from the Bay of Málaga in 1693 accelerated the citadel's decline. After 1675, the citadel deteriorated. Between 1733 and 1735, Alcazaba governor Francisco Antonio de Unzaga Amézaga y Aperribay allowed commoners to attend mass in the chapel-mosque of San Gabriel de la Alcazaba's oratory. The governor requested the king's permission to restore this chapel in Calle del Zagal near the Roman theater, which was severely destroyed in the 1693 earthquakes.

The Secretary of State, Manuel Godoy, built the Royal Hospital of San Luis there after 479 Frenchmen were imprisoned there during the War of Roussillon in 1794. The external walls and part of the interior enclosure were used to build a farmhouse. Restoration began in the 1930s.