En 647, les cavaliers arabes et musulmans mènent leurs premières incursions en Ifriqiya. Le Tell, pays montagneux et difficilement accessible à la cavalerie, reste en marge durant le premier siècle de la conquête. Les informations qui traitent de cette période sont rares et éparses : pour la Kabylie orientale, par exemple, on sait que Mila fut prise en 678, avant Constantine, sans que l'on puisse dater exactement la chute de cette dernière, qui était pourtant un centre économique majeur ; plus à l'ouest, dans les montagnes qui entourent Saldae (Béjaïa), l'opposition à laquelle les conquérants se heurtent est telle qu'ils baptisent la région el aadua, « l’ennemie ». Ici, comme ailleurs sous l'impulsion de chefs tels que Koceila ou Kahena, les tribus berbères, parfois alliées aux Byzantins, résistent pendant plusieurs décennies avant que le califat omeyyade, en 710, puisse faire du Maghreb entier une de ses provinces. Comme ses prédécesseurs, le nouveau pouvoir pèse d'abord sur les populations citadines. Cependant la religion des conquérants progresse rapidement. Le souci d'échapper à l'inégalité juridique et fiscale qui frappe les non-musulmans joue sans doute un rôle important dans les conversions ; il peut aussi y entrer, comme auparavant dans l'adhésion au donatisme, une composante de protestation sociale. En 740, des tribus autochtones se révoltent contre la politique fiscale et la traite des esclaves conduites par les représentants de Damas ; de l'Atlas marocain jusqu'à la Libye, les armées berbères rassemblées au nom de l'égalitarisme kharidjite reconquièrent sur les troupes du calife sunnite la plus grande partie de l’Afrique du Nord, d'où la présence arabe disparaît pour un temps.

En Kabylie, la période du viiie au xie siècle voit se côtoyer, sur un territoire qui s'étend alors de Cherchell à Annaba et de la Méditerranée aux premières montagnes sahariennes, trois groupes de tribus berbères aux dialectes proches et généralement alliés : à l'est de la Soummam, les Kutamas ; à l'ouest de Dellys, les Sanhadjas ; entre eux, les Zouaouas. Le peuple kutama, fort d'une population nombreuse, acquiert une position d'arbitre dans diverses luttes entre factions arabes ou berbères, puis vis-à-vis de l'émirat aghlabide (institué en 800 et premier pouvoir dynastique autonome au sein du califat abbasside), et sait en tirer parti. Ainsi, selon Ibn Khaldoun : « Rien ne changea dans sa position depuis l'introduction de l'Islamisme jusqu'au temps des Aghlabides […] Fort de sa nombreuse population le peuple kutamien n'eut jamais à souffrir le moindre acte d'oppression de la part de cette dynastie. »

Après avoir fait bon accueil aux prêches millénaristes du dai ismaélien Abu Abd Allah, les Kutamas soutiennent la constitution, au début du xe siècle, du califat chiite des Fatimides. Au service de cette cause, ils font la conquête de l'Ifriqiya, puis de l'Égypte. En 969, ils y fondent Al-Kahira (Le Caire) et la mosquée Al-Azhar. Une fois établis en Égypte, les Fatimides laissent aux Zirides, famille alors à la tête de la confédération sanhadja, la charge de défendre le Maghreb contre les tribus zénètes, alliées du califat de Cordoue. La nouvelle dynastie s'installe en Ifriqiya. Par la suite, sa branche hammadide s'en détache et prend le contrôle du Maghreb central, qu'elle place en 1015 sous l'obédience abbasside. En 1048, à leur tour, les Zirides d'Ifriqiya reconnaissent la légitimité du califat de Bagdad et rompent avec le chiisme. En représailles, les Fatimides envoient les Arabes Beni Hilal au Maghreb, qu'ils leur donnent en fief.

En 1067, pour mieux se protéger des attaques hilaliennes, mais aussi mieux tirer parti d'une évolution des échanges favorable au commerce méditerranéen, les Hammadides construisent sur le site de Saldae la ville de Béjaïa. Ils y déplacent leur capitale, précédemment établie à la Kalâa des Béni Hammad, fondée soixante ans plus tôt dans le Hodna. Pour relier les deux cités est construite une route encore appelée de nos jours abrid n'soltan, « l'itinéraire du roi ». Entretenant avec l'Europe des relations commerciales soutenues, centre politique du « royaume de Bougie », Béjaïa, qui acquiert le surnom de « perle de l'Afrique », est aussi un foyer de savoir et de culture dont le rayonnement s'étend à l'échelle de la Méditerranée, rivalisant avec Cordoue. C'est à travers elle, par l'intermédiaire du mathématicien italien Fibonacci, venu y étudier, que les chiffres arabes et la notation algébrique sont diffusés en Europe. C'est aussi un centre religieux de premier plan, « la petite Mecque de l'Afrique du Nord », lieu de résidence de nombreux savants et mystiques. Certains deviennent des saints vénérés par la population locale, comme Sidi Boumédiène, dont le nom est encore honoré dans le Maghreb contemporain. Cependant la tolérance envers les non-musulmans est réelle, comme en témoigne la correspondance entre le sultan hammadide Al Nacir et le pape Grégoire VII.

C'est à proximité de Béjaïa que se rencontrent vers 1120 Abdelmoumen, alors jeune étudiant dans la cité, et Ibn Toumert, réformateur religieux qui en a été expulsé, dont il devient le disciple avant de prendre à sa suite la tête du mouvement almohade122. Parti de « l'extrême Maghreb » (l'actuel Maroc), il s'empare de Béjaïa en 1151 et défait les Arabes hilaliens l'année suivante près de Sétif123. Renversant les royaumes en place, la dynastie qu'il fonde rassemble sous une autorité unique le Maghreb et une partie de la péninsule Ibérique124. Dans la seconde moitié du xiiie siècle, l'empire almohade s'effondre à son tour et laisse la place à une tripartition du Maghreb entre Mérinides (Maroc actuel), Zianides (Maghreb central) et Hafsides (Ifriqiya). L'espace compris entre Béjaïa, dans l'orbite du pouvoir hafside de Tunis, et Dellys, jusqu'où s'étendent depuis Tlemcen les possessions zianides, devient enjeu de rivalités entre les deux royaumes. Au cours des deux siècles suivants, les États maghrébins, en conflit permanent, font venir en renfort tantôt des mercenaires européens, tantôt les tribus arabes, jusque-là cantonnées plus au sud. De plus en plus affaiblis par leurs rivalités et les batailles de succession internes, ils finissent par laisser se constituer dans les villes principales des centres de pouvoir pratiquement autonomes, tandis que les campagnes sortent de tout contrôle125.

Prise dans son ensemble, la période qui va de la seconde moitié du xie jusqu'au xive siècle montre, sous l'effet des attaques hilaliennes et de l'emprise des dynasties successives, une réduction continue du domaine contrôlé par les trois confédérations tribales. Les pourtours ouest, sud et est des montagnes kabyles, plus ouverts, sont les plus rapidement touchés. À l'approche de l'an 1400, seule la confédération centrale, celle des Zouaouas, maintient encore son existence. Elle a perdu ses terres des Hauts Plateaux mais hérite d'une partie de celles de ses anciennes voisines, dont elle accueille les réfugiés. Dès lors et au cours du siècle qui suit, son autonomie se consolide sur un territoire compris, d'ouest en est, entre les oueds Boudouaou et Agrioun, et de la Méditerranée jusqu'à une ligne joignant Sidi Aïssa à Sétif98.

Par ailleurs, plusieurs historiens ont relevé dans les sources médiévales la trace qu'il a existé, entre les tribus et l'État berbère musulman hammadide puis hafside, une relation « harmonieuse », qui montre qu'il n'était pas pour elles un corps étranger, que Béjaïa était « leur propre capitale » et qu'en retour elles étaient à la base de la puissance étatique. En témoigne leur mobilisation pour défendre le Béjaïa hammadide contre les Almohades, puis aux côtés de ses Hafsides tentant de s'affranchir de ceux de Tunis, ou contre les incursions zianides, mérinides et, pour finir, espagnoles126.