W połowie VI w. Malaga, podobnie jak całe południowe wybrzeże półwyspu, przeszła we władanie Bizancjum Justyniana. Wraz z objęciem korony wizygockiej przez Leowigilda, rozpoczęła się ekspansja Wizygotów na południe. Malaga została zdobyta w 571 r. Ten okres to czas silnego konfliktu religijnego między rdzenną, katolicką ludnością, a ariańskimi Wizygotami. Przeciw arianizmowi występował Sewer, biskup Malagi. To pierwsza znana z imienia osoba związana z miastem. Konflikty zakończyły się wraz z koronacją syna Leowigilda – Rekkareda, który zdecydował o przejściu na katolicyzm.
W 711–712 Musa (muzułmański gubernator Afryki Północnej) i jego dowódca, berberyjski wyzwoleniec Tarik, przekroczyli Gibraltar i rozpoczęli muzułmańską inwazję Płw. Iberyjskiego. Malaga padła podczas wojennej ekspedycji syna Musy, Abd al-Aziza w 716, i od tego czasu aż do XV stulecia znajdowała się pod władaniem muzułmanów.