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