La conquête militaire arabe du Maghreb qui a duré de 641 à 711, est lente et difficile. La résistance était plus marquée dans les Aurès et la région de Tlemcen, où les Berbères s'organisent en structure étatique. Les Arabes sont également repoussés par les troupes du royaume des Djédars et les dernières garnisons byzantines. Les figures les plus connues de ce conflit sont le prince guerrier Koceila, qui vainc Oqba Ibn Nafaa en 689, près de Biskra, puis la reine guerrière Kahena, appellation donnée par les Arabes signifiant « devineresse » (Dehia de son vrai prénom), qui est à la tête des Berbères des Aurès. En 693, elle inflige près de Meskiana, une sévère défaite au corps expéditionnaire arabe de Hassan Ibn Numan, qu'elle repousse jusqu'en Tripolitaine. Mais elle est vaincue par la suite.

Dans le Maghreb central, les kharidjites œuvrent efficacement à l'islamisation des territoires. Au viiie siècle, les insurrections se multiplient contre les Omeyyades, en raison des impôts imposés aux Berbères et qui sont, en principe, réservés aux non-musulmans. L'Islam se diffuse ensuite depuis les mosquées, les centres de savoir religieux tel que Tahert et Kairouan, les ribats et les zaouïas. La conversion définitive des Berbères s'achève au ixe siècle, mais des ilots de christianisme subsistent jusqu'au XIIe siècle.

Le processus de l'arabisation est plus long. La diffusion de la langue arabe est d'abord l'œuvre des miliciens arabes qui s'installent notamment dans les forteresses byzantines du Constantinois puis à partir des cités telles que Tahert et Tlemcen. L'usage de cette langue devient plus répandu avec l'arrivée des tribus des Arabes hilaliens dans les plaines, les hauts plateaux et le désert. Plus tard, les immigrés andalous et les confréries religieuses contribuent à d'autres avancées de l'arabisation. Le berbère subsiste dans les massifs montagneux notamment en Kabylie, les Aurès, le Dahra et l'Ouarsenis.

Dynastie fatimide - Dynasties sanhadjiennes - Almoravides et Almohades - Hafsides et Zianides.