La caída de Roma tras la de los vándalos y la inestabilidad durante el período bizantino entrañaron la reconstitución de alguno de los principados bereberes. Algunos, especialmente por el oeste, resistieron la llegada de los musulmanes entre los años 670 y 702.

Los personajes más conocidos de este conflicto fueron el rey cristiano Kusayla, que venció a Sidi Ocba ibn Nafaa en el año 689, cerca de Biskra, y la reina guerra Kahena, cuyo verdadero nombre era Dihya, que a la cabeza de los bereberes, infligió, en la batalla de Meskiana de 693, una severa derrota en el cuerpo expedicionario del emir Hassan Ibn en Noman, a los que alejará hasta Trípoli.

Tras la conquista musulmana, los ciudadanos del territorio adoptarán la religión islámica (para protegerse contra los ataques de los nómadas) y progresivamente adquirirán la lengua árabe. Bereber, fenicio, latín, árabe, español, turco, francés: la mezcla de lenguas, el «mestizaje lingüístico», es intenso, dando lugar al árabe argelino (y al árabe magrebí en general) que se mantiene hasta nuestros días.

La primera parte de la conquista musulmana de España fue conducida por un contingente bereber compuesto casi en su totalidad por conversos, desde el jefe Táriq ibn Ziyad, que dio su nombre al peñón de Gibraltar (جبل طارق, «Djebel Tariq»). Tras el éxito de Tarik, el califa le hizo encadenar y murió en el camino.

En el siglo X, Ubayd Allah al-Mahdi fundó la dinastía fatimí, en la baja Cabilia, donde encontró un eco favorable a sus prédicas milenaristas. Los fatimíes establecieron su autoridad en África del norte entre 909 y 1171 y fundaron un califato disidente de los abasidas de Bagdad.

Este reino estuvo marcado por numerosas revueltas jariyíes (jariyismo), especialmente la de Abu Yazid encabezando las tribus bereberes en el 944, y que infligió la más severa victoria contra la armada fatimí, debilitada y vulnerable, tomando la ciudad de Kairouan.

La revuelta fue vencida por Ziri ibn Manad, a la cabeza de las tribus Sanhadjas, que por salvar el imperio recibió el puesto de gobernador del Magreb central.