La pressione esercitata sull'Impero Romano d'Occidente dalle invasioni barbariche (in particolare dai Vandali e dai Visigoti in Iberia) nel V secolo d.C. ridusse il controllo romano e portò all'istituzione del Regno Vandale dell'Africa settentrionale nel 430 d.C., con la sua capitale a Cartagine. Un secolo dopo, l'imperatore bizantino Giustiniano I mandò (533) una forza sotto il generale Belisario che riuscì a distruggere
il regno dei Vandali nel 534. Il dominio bizantino durò 150 anni. I Berberi contestarono l'estensione del controllo bizantino.