Après la conversion de l'empereur Constantin, au IVe siècle, le christianisme s'était développé dans les régions romanisées, c'est-à-dire essentiellement les villes et les plaines côtières. Ces régions, cependant, qui supportaient mal l'omnipotence des fonctionnaires de l'Empire et l'extrême centralisation de celui-ci, allaient faire bon accueil aux idées d'indépendance financière et commerciale apportées par l'islam. Cette religion de marchands prônait l'égalité entre tous les croyants et, manquant de cadres administratifs, les prenaient chez les « mawalis » (affranchis, clients), lettrés chrétiens et juifs locaux, dont beaucoup finirent par se convertir, échappant ainsi à l'imposition touchant les « dhimmis » — les gens du Livre, chrétiens et juifs, protégés par l'islam, mais soumis à des taxes pour compenser l'interdiction qui leur était faite de porter les armes.
Il semble que, dans leur offensive contre les Byzantins, les troupes arabo-musulmanes conduites par Oqba ibn Nafi atteignirent l'Atlantique dès 682. Mais les tribus berbères montagnardes, qui n'avaient pas plus accepté la domination de Byzance que celle de Rome, les forcèrent à se replier. La véritable conquête débuta une vingtaine d'années plus tard, entre 705 et 707, sous la direction de Moussa ibn Noçaïr qui sut habilement jouer des clivages entre tribus berbères. Ce fut un Berbère converti, Tarik ibn Ziyad, qui franchit le détroit de Gibraltar et conquit l'Espagne. Ses troupes étaient composées principalement de Berbères islamisés, encadrés par des Arabes ou des convertis arabisés.
Plusieurs dynasties musulmanes, se référant pour des raisons religieuses et de prestige à une origine arabe, régnèrent alors sur le pays. La résistance à l'islamisation et à la domination arabe fut vive dans certaines régions berbères. Elle prit notamment la forme du kharijisme, un mouvement musulman contestataire s'appuyant sur une stricte lecture du Coran et récusant le mode de succession au califat, qui privilégiait l'appartenance à la lignée du Prophète ou à celle des premiers compagnons (Ansars). En 742, une révolte ébranla les montagnes marocaines. Dans le Tafilalet (région actuelle d'Erfoud, dans le Sud-Est), un royaume kharijite subsista longtemps avec pour capitale Sijilmassa, comptoir commercial au croisement des routes d'échanges entre les empires de l'Afrique noire — Ghana et Mali — et le monde musulman. En 788, Idris Ier, descendant d'Ali, gendre du Prophète, qui avait fui l'Arabie, fonda la dynastie des Idrissides. Elle régna jusqu'en 926 et fut à l'origine de la ville de Fès, qui devint un important centre religieux et intellectuel sous le régne d'Idris II. Après la mort de celui-ci, le royaume idrisside entra en déclin. Alors que l'Est subissait les raids des nomades Beni Hilal, les Fatimides chiites d'Égypte et les Omeyades de Cordoue rivalisaient pour étendre leur domination sur le Maroc. Si les Fatimides portèrent le coup fatal à la dynastie idrisside, ce fut du Sahara que vint le redressement.