ففتح طرابلس سنة 23 هـ/643 م. ويعود عمرو إلى مصر ويتوفى الخليفة عمر ويخلفه عثمان فيولى على مصر عبد الله بن سعد بن أبى سرح ويستأذن عثمان فى غزو إفريقية التونسية، واذن له، وانضم إلى جيشه بعض أبناء كبار الصحابة، ودق الجيش أبواب إفريقية التونسية سنة 27 هـ/647 م واستولى على مدينة قابس. وكان جريجوريوس قد عرف أن العرب لا بد أن يغزوا دياره وكان قد ترك عاصمته قرطاجة واحتمى بحصن أنشأه الروم فى الداخل جنوبى القيروان يسمى سبيطلة خوفا من أن يهاجمه بقرطاجة أسطول الروم، وجمع إليه جيشا ضخما من الروم وغيرهم استعدادا لمنازلة العرب وسرعان ما أداروا معه معركة حامية، ودارت عليه وعلى جيشه الدوائر وقتل فى المعركة، قتله عبد الله بن الزبير، وكانت معركة حاسمة، قضت على الروم فى إفريقية التونسية وفتحت بلدانها أبوابها للجيش العربى إلا ما كان من قرطاجة فقد ظلت بها حامية رومية، ورجع ابن أبى سرح إلى مصر وترك عليها نافع بن عبد القيس الفهرى، ويولى عليها عثمان سنة 34 للهجرة معاوية بن حديج، ويبدو أنه عاد منها أيام فتنة عثمان، وأعاده إليها معاوية بن أبى سفيان، فنازل الروم فى بنزرت وركبوا البحر فارّين، وولاها بعده معاوية عقبة بن نافع سنة 50 هـ/671 م وكان قد شهد فتح برقة وطرابلس وقابس والديار التونسية، وكان قائدا حربيّا ممتازا بعيد النظر، فرأى أن يتخذ لجيشه العربى مدينة تكون مستقرا له ودارا لا يبرحها، وأخذ توا فى بناء مدينة القيروان أى المعسكر وأتمها سنة 55 هـ /676 م وبنى بها المسجد الجامع ودار الإمارة ودورا لقواده وجنوده، وبنى حولها سورا منيعا، وأصبحت عاصمة للمغرب. غير أنه لم يلبث أن عزل وولى المغرب بعده أو بعبارة أدق إفريقية التونسية أبو المهاجر، وصمم على فتح نوميديا أو القسم الشرقى من الجزائر، وتقدم فيه بجيشه حتى بجاية، وواصل سيره إلى موريتانيا الشرقية حتى تلمسان، وهو ينشر الإسلام، وسكان الجزائر يقبلون عليه.
ومضى يتغلغل فيها وكانت الزعامة بها حينئذ لقبيلة أوربة ورئيسها كسيلة، وكان قد جمع الجموع من البربر والروم، والتقى به أبو المهاجر فى تلمسان ودارت بينهما معركة حامية الوطيس انهزم فيها جيش كسيلة، ووقع فى الأسر، فعامله أبو المهاجر معاملة كريمة جعلته يعتنق الإسلام، وأخذت أفواج من قبيلته الكبيرة تدخل فيه. وعزل أبو المهاجر سنة 62 هـ/683 م وتولّى مكانه عقبة بن نافع، وكان قائدا حربيا باسلا، غير أنه لم يكن سيوسا، فأساء إلى كسيلة مما جعله يصرّ على الانتقام منه، واستخلف عقبة على القيروان زهير بن قيس البلوى وخرج إلى الجهاد فى سبيل الله، فاقتحم بلاد الزاب فى وسط الجزائر يحالفه النصر، ومضى يفتح بقية الجزائر والمغرب الأقصى حتى طنجة قاعدته، وفتح السوس الأدنى والأقصى واتجه إلى المحيط فبلّ قوائم فرسه منه، ونادى ربه قائلا: «اللهم إنّي أشهدك أنى وصلت براية الإسلام إلى آخر المعمورة حتى لا يعبد أحد سواك» وفى عودته رصده كسيلة وقومه، حتى