La caída de Bobastro da paso al sistema islámico con la proliferación de alquerías en el mundo rural, así como la intensificación del regadío. El califato de Córdoba brilla con prosperidad hasta el año 976 en el que muere Al-Hakén II y sube al trono su hijo menor de edad. La crisis política da lugar al fraccionamiento de los reinos de taifas y en ellos, como sabemos, había diversos califas. En este período se construye la Alcazaba de Málaga, siendo uno de los momentos más importantes de la ciudad. Málaga llegó a ser capital de la taifa hammudí así como de otros tres efímeros reinos posteriormente. 

Málaga, por tanto, fue capital de su propio reino cuatro veces. De esta época quedan trazas en el centro histórico y en dos de sus principales monumentos: la alcazaba y el castillo de Gibralfaro. Este castillo fue construido durante el siglo XIV por Yusuf I sobre un anterior recinto de origen fenicio que también contenía un faro que da nombre al cerro, Gíbal al-faruh o monte del faro. Está unido a la alcazaba por un pasillo resguardado por murallas llamado La Coracha.

A los pies de Gibralfaro se encuentra la alcazaba como significativa fortificación palaciega de la época islámica. La Alcazaba fue construida en su mayor parte en el siglo XI, a instancias del rey de taifas bereber de Granada, Badis ben Habús, sobre una antigua fortificación de origen fenicio-púnico y tenía por lo tanto dos funciones: la primera defensiva y militar y la segunda residencial y palaciega. En ella habitaron gobernantes musulmanes y, después, reyes cristianos. De hecho, anteriormente a Badis ben Habús, la dinastía hammudí como últimos califas de Córdoba y reyes de la taifa de Málaga trasladaron durante la fitna de Al-Ándalus la corte califal a Málaga y utilizaron el recinto de la alcazaba y sus estancias como residencia palaciega.

En su construcción se emplearon materiales de acarreo y se reutilizaron piezas del anexo teatro romano de la época de Augusto, como columnas y capiteles. Contaba con matacanas, torres albarranas con saeteras y murallas almenadas como elementos defensivos, sin embargo su mejor defensa estaba en su situación, dominando desde sus balcones la ciudad y la bahía.

El arco de entrada de la zona de ingreso al recinto superior, rodeado por un alfiz de ladrillos, descansa sobre pilastras y tiene clave de piedra, que estuvo dorada, en la cual se labró en hueco una llave. En la estancia alta había un matacán, como así atestiguan dos ménsulas de piedra que sobresalen en el muro. La bóveda del pasadizo es vaída y de ladrillo. En las jambas del arco interior quedan restos de piedra numulítica, de la obra del siglo XI. La puerta fue reconstruida a finales del siglo XIII, como demuestra la llave esculpida en la clave del arco de ingreso.

En el interior de esta alcazaba se encuentra el barrio árabe mejor conservado de la península ibérica, tratándose de ocho viviendas del siglo XI. Ha permanecido intacto gracias a su ubicación, en la parte oriental del amurallado. Se sabe que los muros tenían 1 m de altura, aunque no todos, y estaban enlucidos interior y exteriormente con una espesa capa de cal. Las calles tenían además algunos zócalos decorativos, algo que ha servido para su datación. Las casas, en torno a los 40 m2, tenían un pequeño patinillo, y un acceso en forma de L que mantenía a sus moradores lejos de miradas indiscretas. Tienen un sistema de cañerías que si tirabas un cubo de agua se perdía de forma inmediata, dando prueba de lo avanzados que estaban en sentido sanitario en época andalusí. No están abiertas al público junto al resto de la alcazaba.

Los almorávides se establecieron en Málaga en el año 1092 y los almohades en 1146. En el año 1279 la ciudad es conquistada por Muhammad II ben Al-Ahmar y pasa al reino nazarita. Su reforma le confiere una profunda impronta como edificación nazarí construida sobre la roca. Conjuga las necesidades de defensa y la belleza de un palacio árabe organizado a base de patios rectangulares y crujías en torno con sus jardines y estanques. Se puede también apreciar en sus estancias que, en la tradición de la arquitectura granadina, buscan en los interiores la alternancia de luces y sombras para conseguir esos juegos que tan bien dominaron los alarifes musulmanes.

El recinto superior, al que solo se accede a través de la "puerta siete arcos" abierta en la torre de los denominados Cuartos de Granada, está protegido en su otro extremo por la gran torre del Homenaje. Esta puerta de ingreso a la fortaleza, a juzgar por el arco monumental al estilo de los de Madinat Al-Zahra, fue rellenado y macizado por los nazaríes. El recinto está ocupado íntegramente por el palacio (que en realidad son dos, los restos de uno taifal y el nazarí) y el barrio castrense con las ocho viviendas del siglo XI, así como los baños, el actual taller de restauración y el aljibe. 

En la parte central del recinto superior se encuentran los denominados Cuartos de Granada, donde vivían los reyes y gobernadores. La arquitectura aquí es de estilo nazarí. En los muros de las salas y habitaciones, reconstruidas, existen pequeñas alacenas para exhibir fragmentos de cerámica musulmana hallados en las excavaciones. 

Hay tres patios subsistentes que tuvieron en sus lados pórticos abiertos por tres arcos, siendo mayor el del centro como disposición típica de los patios islámicos andaluces. Del primero de ellos, el más pequeño, sólo está reconstruido el pórtico sur, con tres arcos de herradura, que descansan sobre dos columnas intermedias de mármol. Este pórtico pertenece a la reconstrucción realizada durante los siglos XIII o XIV. En comunicación con él, existe un pequeño pabellón también reconstruido, abierto en sus cuatro frentes por arcos lobulados de yeso entrecruzados que recuerdan los del salón rico de Madinat Al-Zahra.

Contaba la ciudad de Mālaqa con dos arrabales fuera de las murallas, El Perchel y la Victoria, así como un comercio que poseía un discreto radio de acción con el actual Marruecos y una clase media dedicada a la artesanía y al comercio. La tradición ceramista en Málaga se consolidó durante la época andalusí, con la llamada cerámica dorada, aunque sus orígenes son más antiguos. Cabía destacar también la alfarería con vasijas, macetones o candiles. La ebanistería artesanal goza aún de gran reconocimiento y también la ciudad conserva una gran tradición en el trabajo del metal, especializado en la cerrajería artística que frecuentemente se exporta a Oriente Medio.

La ciudad de Málaga fue incorporada finalmente a la corona de Castilla en el año 1487 habiendo supuesto un episodio sangriento en la guerra final contra el reino nazarí de Granada. El asedio de Málaga fue uno de los más largos de la llamada reconquista, duró 6 meses y cortó el suministro de alimentos. La ciudad se rindió finalmente al sucumbir por hambre y sed, pero su población fue castigada a la esclavitud o a la pena de muerte por los llamados reyes católicos.

Existía un acceso al haza de la alcazaba, un espacio amplio y amurallado hasta el siglo XIX en que fue demolido, que cerraba el recinto por el lado del mar, apoyándose en muchos casos sobre espolones rocosos que se adentraban en el agua. En esta zona se encontraba el atarazanal viejo, las atarazanas de la propia alcazaba o el llamado arsenal de la Armada, lugar de protección para los barcos con puertas hacia el mar.