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