لم تتح الفرصة لمعاوية بن حديج أن يعود إلى "إفريقية" لاستكمال الفتح، إذ عزله الخليفة معاوية بن أبي سفيان عن قيادة الجند "عام 48هـ/ 668م" وعين بدلا منه القائد المجاهد عقبة بن نافع الفهري "عام 50هـ/ 668م".
ويتفق المؤرخون على أن بداية ولاية عقبة بن نافع الفهري تمثل مرحلة جديدة من مراحل الجهاد الإسلامي في منطقة المغرب، وكان اختياره موفقا إلى حد بعيد، ونابعا من قناعة تامة بأنه هو القائد الجديد رجل المستقبل في مرحلة انتهت بها حرب الاستكشاف والسرايا العادية لتبدأ مرحلة ذوي الكفاءات العسكرية من الفرسان الموهوبين؛ مرحلة الفتح الثابت المستقر. ولقد توفر في عقبة من الكفاءات الحربية والخلال الدينية ما يجعله جديرا بحمل هذا العبء الثقيل، حيث مكنه طول عهده بإفريقية، وكثرة اشتغاله بحروبها من تنمية مواهبة الحربية، وتكوين فكرة واضحة عن هذه البلاد التي جال في ربوعها، والتعرف على الكير من أخلاق وعادات أهلها، والتفطن إلى أمثل السبل لفتحها وإخضاعها، وكان رجلا قوي الإيمان، ورعا تقيا، تميل نفسه إلى الجهاد في سبيل الله ونشر الإسلام والدعوة إليه، لا إلى مجرد الفتوح والانتصارات وما وراء ذلك من مكاسب1.
وقد تأكد لعقبة بن نافع أن فتح "إفريقية" وبقية المغرب لا يثبت إلا بأمرين.
أولهما: إنشاء مركز للمسلمين تعسكر فيه جيوشهم، ويأمنون فيه على أموالهم