La fin de l'Antiquité, ou Antiquité tardive, est marquée en Afrique du Nord par la chute de l'Empire romain sous le coup des migrations germaniques, des invasions barbares : arrivée des Vandales en 429, et royaume des Vandales et des Alains (en latin Regnum Vandalorum et Alanorum) (435-534), converti au christianisme sous sa forme arienne. vignette|Ruines du mur byzantin de Tébessa, l'une des nombreuses cités fortifiées par les Byzantins Le début du Moyen Âge en Algérie se caractérise par la réaction des Byzantins (Empire byzantin), défenseurs de la romanité : par la guerre des Vandales (533-534), Bélisaire reconstitue l'Afrique romaine (ou la Maurétanie césarienne), intégrée dans l'Empire byzantin : préfecture du prétoire d'Afrique (534-585), Exarchat de Carthage (585-698).
À l'intérieur des terres, des résistances anciennes s'organisent : royaume des Maures et des Romains (429-578), royaume d'Altava (578-708), royaume du Ouarsenis (430-535), royaume de l'Aurès (484-703).
Puis, l'expansion de l'islam est rapide, avec la conquête musulmane du Maghreb (647-709), qui amène au pouvoir le Califat omeyyade Damas et Harran (661-750), puis l'émergence de dynasties berbères musulmanes.
À la fin de Moyen Âge, en prolongement des croisades chrétiennes en Hispanie, le débarquement des Espagnols conduit à l'intervention des Turcs Ottomans et la fondation de la Régence d'Alger..
Division de l'Empire romain et reconquête byzantine
Au moment où l'Empire romain se divise progressivement en deux, l’Empire romain d'Orient, ou Empire byzantin, est apparu vers le dans la partie orientale de l'Empire romain..
Jean Troglita, général byzantin du s'illustra notamment contre les Perses et les Berbères. Ce fut également un lieutenant du grand général byzantin Bélisaire, vainqueur des Vandales en Africa et des Ostrogoths en Italie dans les années 530. Solomon est un gouverneur byzantin de la première moitié du . En 534, il est nommé par l'empereur byzantin Justinien comme gouverneur de l'Afrique, tout juste reconquise par le général Bélisaire sur les Vandales de Gélimer. Il est remplacé deux ans plus tard (536), avant de retrouver son poste en 539. Il doit faire face aux rebelles berbères, notamment ceux du chef Antalas. Il est toutefois battu par ces derniers dans une bataille près de la cité de Theveste (actuelle Tébessa) en 544, trouvant la mort au combat. Iaudas se révolte contre l'autorité byzantine dans les Aurès, il se proclame roi des Aurès.
Deux personnalités Berbères des Aurès furent des chefs byzantins, Ifisdaïas et Cutzinas pendant le commandement de Jean Troglita, ce dernier voulait attaquer les Berbères du Sud après que les Aurès et le Zab furent dominés par les byzantins grâce à Salomon byzantin. Par contre Mastigas fut un roi berbère de la Maurétanie césarienne. Après les Vandales, il prend en main une partie de la Maurétanie césarienne, mais il est certain que les Byzantins sont arrivés jusqu'à Frenda, car il y a des inscriptions byzantines sur place en Algérie.
En 544, les Byzantins exerceront un pouvoir jusque dans la province de Constantine. Cependant, l'émergence d'insurrection berbère contre les Byzantins provoque l'organisation de plusieurs États puissants dont les Djerawa, les Banou Ifren, les Maghraouas, les Awarbas, et les ZénètesAlgérie, le passé revisité. Par Chems-Eddine Chitour. Publié par Casbah Editions, 1998. , p 212. Et, selon Corripus dans la Johannide, à l'époque de Jean Troglita sous le règne de Justinien entre 547 et 550, Les Banou Ifren(Ifuraces)Revue africaine, numéros 181-191 Par Société historique algérienne,page 270 livre en ligne faisaient la guerre aux ByzantinsEncyclopédie berbère, volume 24 Par International Union of Prehistoric and Protohistoric Sciences,International Union of Anthropological and Ethnological Sciences,Laboratoire d'anthropologie et de préhistoire des pays de la Méditerranée occidentale (France), page Page 3649.
Au début de la conquête musulmane en Afrique du Nord, Koceila, roi berbère, s'allie avec les troupes byzantines. Après sa mort la reine berbère, Kahina, attaque les Ommeyades avec l'aide des Byzantins et des cavaliers zénètes. Elle gagne deux fois contre les troupes Ommeyades.
Conquête et expansion de l'islam en Algérie (647 à 776)
La naissance de l’islam au , qui s’accompagne d’un vaste mouvement d’expansion territoriale menant à la formation d’un véritable empire, provoque une reconfiguration de l’espace moyen-oriental. L'Empire byzantin perd une grande partie de ses territoires au Moyen-Orient et en Afrique du Nord au profit des califats musulmans.. En 647, les arabes, commandés par Oqba Ibn Nafaa compagnon du prophète Mahomet, s’établirent sous l’étendard de l’islam, en Algérie. Malgré les premières résistances aux expansionnistes, cependant les tribus berbères adoptèrent plus tard l’Islam massivement et contribuèrent largement à son expansion et à son rayonnement jusqu’en Andalousie..
Ibn Khaldoun dresse un tableau qui résume presque toutes les dynasties importantes en Algérie au Moyen Âge.Histoire des Berbères et des dynasties musulmanes de l'Afrique septentrionale, Ibn Khaldūn, William MacGuckin.
Califat omeyyade (647 à 743)
vignette|300px|Étendue maximale du califat omeyyade, allié des Zénètes
Les Berbères, christianisés par RomeVincent Serralda et André Huard, Le Berbère... Lumière de l'Occident, éd. Nouvelles éditions latines, Paris, 1990 , résistèrent de façon différenciée à la chute de Rome, puis aux Vandales, et à l'instabilité durant la période byzantine. Certains s'enfuirentBernard Heyberger, Chrétiens du monde arabe p5, Ed. Autrement, 2003 en SicileJoseph Cuoq, L'Église d'Afrique du Nord du deuxième au douzième siècle p111, Le Centurion, Paris, 1984.. D'autres, notamment dans les Aurès, vont résister à l'arrivée des musulmans entre 670 et 702. Cette période a entrainé la reconstitution de plusieurs principautés berbères.
Les figures les plus connues de ce conflit furent le roi chrétien Koceila, qui vainquit Oqba Ibn Nafaa en 689, près de Biskra, puis la reine guerrière Kahena (de son vrai nom Dihya), qui à la tête des Berbères (des Djerawas, des Banou Ifren de l'AurèsIbn Khaldoun, histoire des berbères et des Nefzaouas de Libye Tripolitaine, ainsi que des Roums de la côte, infligea, en 693, à la bataille de la Meskiana, une sévère défaite au corps expéditionnaire arabe de l'émir Hassan Ibn Numan, qu'elle repoussa jusqu'en Tripolitaine. Mais elle perdit la bataille suivante en partie à cause de la trahison d'un jeune Arabe qu'elle avait adopté (Khaled) et en partie parce que ses hommes, en pratiquant la politique de la terre brûlée pour décourager l'invasion, suscitèrent l'opposition des cultivateurs Roums qui passèrent du côté arabe. Kahena mourut au combat dans l'actuel Est algérien (Puits de Kahena, « Bir al Kahena »).
De nombreux Berbères se convertirent ensuite en masse à la religion musulmane. Certains adoptèrent même la langue des conquérants, surtout à l'Est de l'Ifriqya. La conquête musulmane de l'Espagne et du sud de la France qui s'ensuivit fut menée par un contingent arabo-berbère comptant beaucoup de récents convertis, à commencer par son chef Tariq ibn Ziyad, qui donna son nom à la colline de Gibraltar (Djebel Tarik). Après un conflit avec le gouverneur du Maghreb Moussa Ibn Noçaïr, Tariq Ibn Ziad fut envoyé enchainé au calife de Damas et il mourut en route.
Quant à l'immigration arabe en Afrique du Nord, elle fut peu importante, sauf dans deux régions extérieures à l'Algérie, celle de Kairouan et celle de Tanger. Il s'y ajouta ultérieurement dans certaines régions du sud l'arrivée de tribus Arabes bédouines nommées Hilaliens.
Kharidjisme berbère (736 à 947)
Les Berbères ne tardent pas à se révolter contre l'autorité du calife d'Orient, autant pour des raisons fiscales que politiques. Plusieurs royaumes berbères autonomes font leur apparition. Dans le Maghreb central, l'un d'eux, la principauté rostémides de Tahert se développe durant 140 ans.
À la suite du grand schisme de l'islam, lorsque Ali, gendre du prophète disputant le califat à Muawiya, accepta une transaction, à la suite de laquelle Muawiya fut vainqueur, l'islam se divisa en deux branches principales : les adeptes de la branche dominante prirent le nom de sunnites et ceux qui se réclamaient d'Ali devinrent les chiites. De ces deux branches, celle qui a finalement prévalu en Afrique du Nord est le sunnisme. Il n'en fut pas toujours ainsi puisqu'au moment du schisme, la branche chiite fut à son tour l'objet d'une scission : certains des partisans d'Ali lui reprochèrent d'avoir accepté le compromis avec Muawiya et de ses hommes quittèrent son armée. Leur tendance prit le nom de kharidjisme.
Le kharidjisme se développa par la suite avec une grande ampleur en Afrique du Nord, où il fut accueilli avec chaleur par de nombreux berbères à Ouargla, à Tlemcen, Tobna, Tiaret, M'Sila. le kharidjisme berbère sufrite et nekarite prit racine non seulement dans la ferveur religieuse, mais aussi dans le mécontentement populaire. Le kharidjisme berbère est basé sur des élections pour désigner les chefs. Un grand désordre et des combats très violents ensanglantèrent l'Afrique du Nord. Ces massacres et ces dévastations entraînèrent, entre autres conséquences, la création du royaume éphémère sufrite de Tlemcen ainsi que les royaumes rostémide et Idrissides, ainsi que l'arrivée au pouvoir de la dynastie chiite des Fatimides.
Quant au kharidjisme, il disparut entièrement de l'Afrique du Nord où il n'a subsisté que dans le Sud algérien, au Mzab. Les actuels originaires du Mzab, ou mozabites, exercent de nos jours, dans le reste de l'Algérie, les activités les plus pacifiques, contrastant particulièrement avec le goût pour le combat de leurs ancêtres.
Révolte berbère d'Abou Qurra (736 à 790)
Vers 736, Abou Qurra des Banou Ifren est élu comme roi des Banou Ifren et comme calife des Berbères kharidjites sufrite. Abou Qurra rassemblera tous les Berbères sous son commandement. Abou Qurra part en guerre contre tous les régimes dynastiques des Omeyades, des Fatimides et des Abbassides. Abou Qurra sort vainqueur de toutes les batailles. Il établira sa puissance dans tout le Maghreb. Il quitte sa fonction après que quelques divergences apparaissent entre lui et ses subordonnants. Abou Qurra retourne à Tlemcen et commande les Banou Ifren. Il invitera Idris à Tlemcen et s'efforcera à pacifier la région..
Dynasties musulmanes berbères et arabes (776 à 1556) Plusieurs dynasties ont régné en Algérie entre les : les Rostémides (776-909), les Idrissides (788-985), les Fatimides (908-972), les Aghlabides (800-909), les Zirides (972-1148), les Hammadites(1007-1152), les Almoravides (1052-1147), les Almohades (1147-1269) et les Zianides (1235-1554). Dynastie rostémide (776 à 909)
droite|vignette|150px|Extension maximale du mouvement religieux kharidjiste qui donna le royaume rostémide de Tahert(776-909) Ibn Rustom prend comme épouse une femme berbère des Banou Ifren et il aura des enfants. Il fonde en 761 un royaume ibadite dans le nord du Maghreb avec Tahert pour capitale. Celui-ci, comme l'émirat de Cordoue depuis sa création en 756, conserve son indépendance du califat des Abbassides, malgré les pressions diplomatiques et militaires ainsi que les pertes de territoires. En 909, en proie à des crises intérieures, le chef chiite et fondateur de la dynastie des Fatimides, Obeïd Allah, mit fin au royaume rostémide.
Dynastie Idrisside 788 à 985
Idris prend comme épouse une berbère dont il aura un enfant : Idriss II. Deux versions des faits : Première version : Abou Qurra invite Idriss vers 790 à séjourner à TlemcenLa médina de Tlemcen: l’héritage de l’histoire, Fouad Ghomari. Seconde version : Idriss regroupe ses alliés et fait une incursion à Tlemcen. Le chef des Maghraouas Mohamed Ibn Khazer fera alors allégeance à Idris vers 790.