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