Les Vandales, ces envahisseurs germaniques débarqués en 429, dominèrent bientôt l´ensemble de l´Afrique septentrionale : en 455, Genséric gouvernait tout le Maghreb romain.
Les Vandales, qui étaient ariens, traitèrent en ennemies l´aristocratie romanisée et l´Église, et en alliés la masse des Berbères qu´ils ne pouvaient contrôler. Les tribus insoumises, les nomades chameliers en profitèrent pour razzier les plaines. Les montagnards de l´Aurès détruisirent toutes les cités du Sud constantinois.
La fragile domination vandale, qui laissa se reconstituer les principautés berbères indépendantes, fut ensuite abattue par les troupes de l´empereur de Constantinople (533). Mais les Byzantins ne reconquirent que la partie orientale de l´Algérie actuelle, et le reste du pays fut abandonné.
Dans la partie byzantine, l´Église recouvra ses biens et son autorité, l´administration releva les ruines des cités et les fortifia hâtivement, mais cette dépendance lointaine du Basileus restait très vulnérable. Elle ne résista pas à l´invasion arabe.
De la longue domination romaine rien ne subsista. La langue latine et le christianisme mirent certes plusieurs siècles à s´éteindre, mais l´Algérie médiévale fut islamisée et arabisée.