الإسلام إلى آخر المعمورة حتى لا يعبد أحد سواك» وكرّ راجعا بعد أن دوّخ القبائل المغربية ودانت له، وكان قد وبّخ كسيلة زعيم قبيلة أوربة فى أول ولايته الثانية لوقوفه قديما ضد الإسلام، وأسرّها فى نفسه هو ومن غضبوا له من البربر الذين لم ينسوا قوميتهم البربرية، وصمّم كسيلة على الثأر، حتى إذا تقدم عقبة جيشه بالزاب فى عودته، وبقى فى نفر قليل معه إذا كسيلة الأثيم يحاصر عقبة مع جمع من الروم ومن قومه سنة ٦٤ هـ/٦٨٣ م ويهجمون عليه وعلى من معه من أصحابه وكانوا نحو ثلاثمائة، وقاتلوهم قتال الأبطال، وتكاثروا عليهم فاستشهدوا جميعا، ودفنوا فى نفس المكان-نضّر الله وجوههم-وأقيم على قبر عقبة مسجد يعرف باسمه، وهو من المزارات الكبرى فى المغرب. واتسعت ثورة كسيلة، وتبعته جموع غفيرة من البربر دخل بها القيروان، وتراجع الجيش العربى بقيادة زهير بن قيس إلى برقة انتظارا لجيش عربى يقدم عليه للقضاء على تلك الثورة، وتصادف أن ثورة عبد الله بن الزبير فى الحجاز كانت قد بدأت وشغل بها مروان بن الحكم حتى إذا أصبحت الخلافة خالصة لعبد الملك بن مروان وهدأت الأمور فى المشرق أرسل إلى زهير سنة ٦٩ هـ/٦٨٨ م جيشا جرارا زحف به زهير إلى كسيلة وجموعه، فمزّقهم شر ممزق، وقتل كسيلة وخلق كثير من البربر، واسترجع زهير القيروان وتعقب المنهزمين فى الجزائر إلى أن أخرجهم منها، وعاد إلى العاصمة ورتّب شئونها، ورأى أن يعود بعد هذا النصر العظيم إلى المشرق، وبينما هو فى نفر قليل من صحبه عند برقة إذا هو يرى بعض سفن للروم وهم يسوقون أمامهم بعض المسلمين، أسروهم على حين غفلة، فنازلهم وكتبت له الشهادة عند ربه، ويقول الرقيق القيروانى عنه:«كان زهير من رؤساء العابدين وكبراء الزاهدين».
وولّى عبد الملك بعد زهير على إفريقية حسان بن النعمان سنة ٧١ هـ/٦٩٠ م وكانت لا تزال للروم جالية كبيرة فى قرطاجة تتجسّس لبيزنطة وتعيث فسادا ضد العرب فحاصر البلدة وفتحها عنوة وأذعن من بها من النصارى، ولم يكد ينصرف عنها حتى تحصنوا بها فعاد إليهم وهدم حصون قرطاجة وأسوارها حتى لا يحميهم منه شئ، وفرّ منها كثيرون إلى البحر المتوسط وما وراءه، وطهّر بنزرت وشمال إفريقية التونسية من الروم وفرض الجزية على من ظل منهم ومن البربر على دينه المسيحى، واشتعلت فى أوائل عهده فتنة فى قبيلة جراوة الزناتية بجبال الأوراس فى الجزائر تزعمتها امرأة بربرية اسمها «دهيا» وسماها العرب الكاهنة، ونازلها حسان سنة ٧٦ هـ/٦٩٥ م ولم يكتب للمسلمين النصر، واضطر حسان إلى التراجع حتى مدينة سرت بليبيا، وظل بها خمس سنوات منتظرا مددا من مصر أو من دمشق، وأتاه فى سنة ٨٠ هـ/٦٩٩ م مدد ضخم فاشتبك مع الكاهنة فى معركة عنيفة قتلت فيها سنة ٨١ هـ وأسلم ابنان لها فجعلهما قائدين لجيش مكون من اثنى عشر ألفا من العرب والبربر، وبذلك دعم نظرية