تعامله مع الدولة البيزنطية التى حاولت أن تحتفظ بالشمال
الإفريقى بعد أن فقدت «مصر» والشام، لكنها لم تنجح، فقد
حقق «أبو المهاجر» نصرا عسكريا عليها، مكنه من السير إلى
الغرب، فاتحا معظم «المغرب الأوسط» - الجزائر الحالية - ووصل
إلى «تلمسان». أعاد الخليفة «يزيد بن معاوية» «عقبة بن نافع»
مرة أخرى إلى «شمالى إفريقيا»، فواصل جهود «أبى
المهاجر»، وقام بحملته التى اخترق بها الساحل كله فى شجاعة
وجرأة حتى بلغ شاطئ «المحيط الأطلسى»، وأوطأ أقدام
فرسه فى مياهه، وقال قولته المشهورة: «اللهم اشهد أنى قد
بلغت المجهود، ولولا هذا البحر لمضيت فى البلاد، أقاتل من كفر
بك حتى لا يعبد أحدا دونك». وفى أثناء عودة «عقبة» من
غزوته المظفرة تعرض لكمين نصبه له البيزنطيون بمساعدة
«كسيلة» زعيم «البربر»، الذى كان «عقبة» قد أهانه، فبينما
هو يسير فى عدد قليل من جنوده يبلغ زهاء ثلاثمائة جندى
انقضت القوات البيزنطية عليه وعلى من معه عند بلدة تهودة
فاستشهدوا جميعا سنة (63ه). ومما أسهم فى وقوع الكارثة
أن «عقبة» قد وقع فى خطأ عسكرى كبير، إذ سرح معظم
جيشه، وأمرهم بالسير أمامه، فابتعد عنه لمسافة طويلة، مما
جعل الجيش البيزنطى ينفرد به ويهزمه هزيمة ثقيلة أضاعت كل
الجهود التى بذلها المسلمون فى فتح تلك البلاد، واضطر
المسلمون إلى الارتداد إلى الخلف، ولم يستطيعوا الاحتفاظ
بالقيروان، وعادوا إلى «برقة». تسلم «زهير بن قيس البلوى»
قيادة الجيش خلفا لعقبة بن نافع سنة (63ه)، وعزم على الثأر
من البيزنطيين و «البربر»، لكنه لم يستطع أن يحقق هدفه إلا فى
سنة (69ه)، نظرا لانشغال الدولة الأموية بالأحداث والفتن
الخطيرة التى حدثت فى الداخل بعد وفاة «يزيد بن معاوية» سنة
(64ه). تحرك «زهير» بجيش كبير وزحف على «القيروان» سنة
(69ه)، والتقى على مقربة منها بجيش «كسيلة»، فهزم «البربر»
هزيمة ساحقة بعد معركة شديدة وفى أثناء عودته إلى «برقة»
للدفاع عنها - بعد ما نمى إلى علمه أن البيزنطيين زحفوا عليها
فى جموع عظيمة - تعرض لهجوم بيزنطى مفاجئ، فلقى حتفه
هو ومن معه. وصلت أخبار استشهاد «زهير» ومن معه إلى
الخليفة «عبدالملك بن مروان» وهو مشغول بصراعه مع الخوارج
والشيعة وآل الزبير، فلم يتمكن من القيام بعمل حاسم إلا بعد أن
استقرت له الأوضاع، فأسند قيادة جبهة الشمال الإفريقى إلى
«حسان بن النعمان» وأمده بجيش كبير من «مصر» والشام، بلغ
عدده نحو أربعين ألف جندى. واستطاع «حسان» بعد جهد جهيد
القضاء على الوجود البيزنطى فى الشمال الإفريقى، وأن يحطم
مدينة «قرطاجنة» أكبر مركز بيزنطى، وأن يبنى محلها مدينة
«تونس» الحالية، كما قضى على كل مقاومة للبربر، بعد أن
حقق نصرا هائلا على زعيمتهم الكاهنة التى آلت إليها الزعامة
بعد مقتل «كسيلة»، ونعم المسلمون بأولى فترات الاستقرار فى
«المغرب». ولم يكن «حسان بن النعمان» قائدا عسكريا عظيما
فحسب، بل كان رجل دولة وتنظيم وإدارة أيضا، فأنشأ
الدواوين، ورتب أمور الخراج والجزية، ووطد سلطان الحكم
الجديد فى الثغور والنواحى، وجدد مدينة «القيروان»، وأنشأ
بها المسجد الجامع، ووضع سياسات مستقبلية انتهت بأهل
الشمال الإفريقى كله إلى اعتناق الإسلام. حل «موسى بن
نصير» سنة (85ه) محل «حسان بن النعمان» فى ولاية شمالى