لم يحلّ عام 62هـ الموافق 681م حتى عُزل أبو المهاجر عن الإمارة وأعيد إليها عقبة، وكان في عهد الخليفة يزيد بن معاوية عقب وفاة مسلمة بن مخلد والي مصر. فواصل عقبة تنفيذ الشطر الثاني من خطته، فوصل في تقدمه إلى شاطئ المحيط، على الرغم مما لقيه من مقاومة عنيفة من الروم والبربر. وقُتل عقبة عند حصن تهودة في طريق عودته إلى القيروان، وقُتل معه أبو المهاجر، وذلك لسوء سياسته. وخشي المسلمون بالقيروان على أنفسهم فأخلاها حاكمها زهير بن قيس عام 65هـ الموافق 684م، وانسحب إلى برقة، فدخلها كسيلة، وأمَّن من بقي بها من المسلمين.
ومكث زهير في برقة أربع سنوات ينتظر المدد لمحو الآثار السيئة لمعركة تهودة. وعندما وصلته إمدادات الخليفة عبد الملك بن مروان وأمره بالتقدم مرة أخرى إلى المغرب عام 69هـ الموافق 688م، تحرك ليصطدم بقوات كسيلة المنسحبة من القيروان لتتحصن بـ ممس. ودارت معركة رهيبة، انتهت بهزيمة البربر، وقْتل كسيلة. ولكن لم يجْن زهير ثمرة نصره، لأنه أخطأ في تأمين ظهره عندما توغّل في داخل البلاد، فباغته الروم في طريق عودته إلى برقة، وقضْوا على جنده، واستُشهد زهير بنفس الطريقة والسبب اللذين استشهد بهما عقبة.
حَرص عبد الملك بعد مصرع زهير على إتمام فتح المغرب محافظةً على هيبة الدولة الإسلامية، فولى عليها حسان بن النعمان عام 76هـ الموافق 695م، وحشد له أربعين ألف مقاتل.
سار حسان إلى المغرب، مجتازًا برقة وطرابلس حتى وصل إلى سهل تونس، حيث انضم إليه عدد كبير من البربر، فقصد بهم قرطاجنة ـ عاصمة الروم ـ فحاصروها ثم افتتحها، وترك بها حامية صغيرة، وانصرف إلى القيروان. وثارت المدينة من خلفه، فعاد إليها وافتتحها عنوة وخَّرب حصونها.