En este momento, Teodomiro aprovecha para levantarse en armas contra los invasores, siendo secundado en Málaga y Almería.
El hijo de Musa, Abd al-Aziz, recién nombrado comandante jefe de las fuerzas árabes en Hispania, se dirige a Murcia para someter a Teodomiro, al cual derrota apoderándose de las comarcas de Murcia y Almería y a continuación pone sitio a Málaga.
De acuerdo a la versión de Francisco Guillén Robles, la ciudad se hallaba bien defendida y el asalto parecía arriesgado.
Sin embargo, la ciudad continuó resistiendo y Abd al-Aziz decide asaltarla durante la noche, aprovechando la oscuridad para escalar las murallas.
No existe unanimidad entre los historiadores sobre este episodio.