عاد عقبة إلى "القيروان"، وكان أول ما فعله هو القبض على أبي المهاجر دينار، وتوثيقه في الحديد، وأخذ ما لديه من أموال "مائة ألف دينار" للإنفاق منها على إعداد الحملة الجديدة، ثم إنه أمر بتخريب معسكره "تكروان"، وجدد ما كان قد خرب من عمارة "القيروان"، ورد الناس إليها، فعمرت وعظم شأنها1، ثم بدأ منها حملة كبرى تختلف عن كل الحملات السابقة. إذ أنه ساح في كل صحروات المغربين -الأوسط والأقصى- حتى وصل إلى سواحل "السوس الأقصى" على البحر المحيط. وقبل الخروج من القيروان قرر عقبة أن يترك فيها حامية عسكرية قدرت بستة آلاف رجل، للدفاع عن المدينة، وحماية ما بها من الذراري والأموال، واختار "زهير بن قيس البلوي" قائدا عليها2، ثم بدأ حملته الكبرى بهمة عالية، وعزيمة لا تفتر، حبا في الجهاد، وتوقا إلى الاستشهاد، وأملا في الانتهاء من فتوحات المغرب التي طال أمدها.
اتجه عقبة نحو مدينة "باغاية" عند أقدم جبل الأوراس، ولقي جمعا كبير من الروم، فهزمهم، ثم زحف إلى "بلاد الزاب" الفسيحة "في المغرب الأوسط" فاكتسحها بعد عدة معارك انتهت كلها بهزيمة الروم، فلما وصل إلى "تاهرت" وجد نفسه أمام تحالف كبير من الروم والبربر لم يعهد المسلمون له مثيلا من قبل، فالتقى بهم في معركة حامية، فأباد فرسانهم وفرق جمعهم، وقطع آثارهم3، واستمر في طريقه غير عابئ بالمقاومة مهما اشتدت، حتى وصل إلى ولاية "طنجة" في المغرب الأقصى. وكان يحكمها أمير من الروم يسمى "يليان4، فأرسل إلى عقبة مهاديا