ثمّ بدأت مرحلة جديدة للحكم الإسلامي ببلاد المغرب على يد موسى بن نصير الذي تقلّد ولاية إفريقية سنة (٨٥ هـ /٧٠٤ م)، وتولّى فتح بعض المناطق التي لم تفتح بعد . كما قام بتسخير عدد من العرب لتعليم البربر مبادئ الإسلام واللغة العربية.

ثمّ أرسل تابعه طارق بن زياد (البربري) لفتح الأندلس. ففتحها سنة (٩٣ هـ / ٧١١م).

ثمّ تعاقبت الولاة بعد ذلك على إفريقية وبسطوا نفوذهم على جميع بلاد المغرب والأندلس.

ومن أبرز هؤلاء :

- عبيد الله بن الحبحاب (١١٦-١٢٣هـ /٧٣٤-٧٤٠م)، وهو الذي بنى جامع الزيتونة بتونس سنة (١١٦هـ /٧٣٤م)

- عبد الرحمان بن حبيب الفهري (١٢٧-١٣٧هـ )، وكان في بدايته ثائراً ضد الحكم الأموي وضد الخوارج على السواء، ثمّ استقلّ بحكم افريقية حوالي عشر سنوات قبل أن يعلن انفصاله على مركز الخلافة العباسية في المشرق.

وكان لانفصاله قصّة طريفة خلاصتها :

أنّه لمّا تولّى المنصور العباسي الخلافة، أقرّ عبد الرحمان على إفريقية، وأرسل إليه خلعة سوداء، فلبسها، وأرسل بدوره إلى المنصور هدية مع كتاب جاء فيه : «إنّ افريقية اليوم إسلامية كلّها، وقد انقطع السبي منها