A principio del siglo VI, tropas bizantinas incorporaron al dominio de Constantinopla en nombre del emperador Justiniano I la zona costera de la provincia, y le sumó parte de la "Baetica" formando una nueva provincia que abarcaba desde el Algarve portugués hasta el sur de la actual provincia de Valencia.