Tras la caída del Imperio Romano, fueron los Visigodos los que terminaron imponiéndose en el territorio de la Bética. Pero los enfrentamientos entre facciones rivales favoreció la entrada de los Bizantinos en ayuda en una de las partes en conflicto, consiguiendo a partir del año 552 una intervención especial en Málaga. En la época de Suintila (621-631), los visigodos recobraron el control de la provincia al conseguir expulsar a los bizantinos.

Los enfrentamientos internos entre visigodos continuaron y, al igual que ocurriera con los bizantinos, la petición de ayuda a los musulmanes por una de las partes en conflicto favoreció la llegada de este pueblo a la península.

Después de la derrota de los visigodos en la batalla de Guadalete, Abdalaziz, hijo de Muza, con un ejército compuesto por bereberes, judíos, esclavos libertos y visigodos renegados, conquista Málaga y penetra en el interior de la provincia tomando núcleos como Nescania. Lo que hoy es la provincia de Málaga quedó incluida en la Cora (circunscripción) de Raya, estableciéndose su capital en Medina Arxiduna (Archidona). Precisamente ésta fue la ciudad elegida por Abderramán para proclamarse emir independiente de Damasco en el 756. Posteriormente este emir elegiría la ciudad de Córdoba como capital de Al-Andalus.

De todas las rebeliones internas que se produjeron entre los nuevos dueños del territorio, hubo una que estuvo a punto de dar al traste con el estado cordobés y que tuvo un especial protagonismo en estas tierras. Fue la sublevación del muladí rondeño Omar Ben Hafsún.

Los muladíes-hispanogodos convertidos al Islam. Se hicieron fuertes en el abrupto territorio de la Serranía rondeña, y establecieron en Bobastro (al noroeste de Ardales) su cuartel general. La rebelión, que se extendió por otras poblaciones como Teba, Álora y Comares, fue finalmente sofocada por Abderramán III, quien en el 929 estableció el Califato de Córdoba.

La ciudad de Málaga, que contaba ya con un importante puerto comercial, fue dotada, a mediados del siglo IX, de una Alcazaba para detener las frecuentes invasiones de los piratas normandos.

Durante el período que duró el Califato de Córdoba, el campo de Málaga se vio favorecido con la introducción de nuevas técnicas agrícolas, especialmente regadíos, y nuevos cultivos (plátanos, granadas, higos, caña de azúcar, etc.). Ciudades como Ronda, Antequera, Vélez-Málaga, Álora, Coín, Archidona y otras muchas, fueron enriquecidas con monumentos por las grandes familias locales y, en general, toda la provincia, como el resto de Andalucía, gozó de un amplio período de paz y prosperidad.

Con la caída del Califato surgieron los Reinos de Taifas y en nuestra provincia aparecen dos muy influyentes: el de Ronda y el de Málaga, posteriormente incorporado al reino de Granada.

A partir del siglo X encontramos en la provincia dos comunidades: la árabe-bereber (en la que se integran los cristianos convertidos al Islam -muladíes- y los que decidieron convivir con ellos) y la mozárabe. Los primeros ocuparon las zonas montañosas, especialmente la Serranía de Ronda, mientras que los segundos, o vivían en los arrabales de las ciudades o en el campo. Los mozárabes eran muy numerosos en la Axarquía, aunque también se extendieron por otras zonas. Se destacan en esta época los núcleos de Jotrón y Santo Pitar (en Málaga), Masmullar (Comares) y Bobastro (Ardales). En la Serranía de Ronda parece que hubo enclaves importantes en Cortes de la Frontera, Alpandeire y Jubrique. También se ha detectado la existencia de eremitas cristianos en Coín, Ronda, Archidona y Bobastro.

Con el fortalecimiento del reino de Granada, Málaga se convirtió en la más importante ciudad comercial de la España musulmana. La ciudad fue engrandecida y fortificada y se construyeron nuevos barrios para dar cabida al gran contingente de emigrantes y refugiados procedentes de las zonas conquistadas por los cristianos.

A mediados del siglo XIV empiezan a ser conquistadas por los cristianos las tierras de Málaga con la caída de El Burgo, Cañete la Real, Ardales y otros lugares, pero la primera conquista importante fue la toma de Antequera en los inicios del siglo XV (1.410) por el regente Don Fernando, conocido como Fernando de Antequera. A él se le atribuye la todavía repetida frase: ¡Que nos salga el sol por Antequera y que sea lo que Dios quiera!, pronunciada antes del asalto definitivo a la ciudad.

Unos años más tarde de la conquista de Archidona, a mediados del siglo XV, se produjo una reacción importante de los musulmanes que alcanzó su momento más álgido en el llamado "desastre de la Axarquía", cuando en 1.483 las tropas de El Zagal, gobernador de Málaga, infringieron una seria derrota al ejército cristiano. Al año siguiente comenzó la ofensiva definitiva sobre la provincia.