ففتح الديار فى الصحراء حتى وصل إلى زويلة حاضرة فزان، واستسلمت سنة ٢٢ للهجرة.
وبعد أن رتب عمرو بن العاص شئون الحكم فى برقة اتجه إلى طرابلس ففتحها سنة ٢٣ للهجرة، واستعان ببعض قواده فى فتح ما بقى من بلدانها وبلدان برقة. وتمّ ذلك كله فى عهد الخليفة العظيم عمر بن الخطاب واستتم عمرو بن العاص فى سنة ٢٣ فتح نفوسة وبذلك عمت ديار ليبيا جميعا أضواء الإسلام. وظل عمرو طوال هذه السنة والسنة التالية أو أكثرها ينظّم شئونها، وترك لأهلها أن يجمعوا بأنفسهم الجزية والضرائب المفروضة ويؤدّوها فى الموعد المضروب. وكانت هذه سياسة رشيدة، ولم تفرض ضرائب فادحة كما كان الشأن أيام الدولة البيزنطية، وأحسّ البربر فى ليبيا بتعاليم الإسلام فى العدل والمساواة المثلى بين من يسلمون منهم وبين العرب، فأقبلوا على الدين الحنيف وأخذ يعتنقه كثيرون منهم. ويعود عمرو إلى مصر مخلفا وراءه ابن خالته عقبة بن نافع. ويتولى الخلافة بعد عمر عثمان بن عفّان، فيولّى على مصر عبد الله بن أبى سرح سنة ٢٥ للهجرة وتظل ليبيا لأيامه هادئة حتى فتنة عثمان سنة ٣٥ للهجرة، فتضطرب الأمور فيها وفيما وراءها من إفريقية التونسية، ويتولّى عمرو بن العاص مصر ثانية لعهد معاوية. ويعنى معاوية ببرقة وطرابلس وإفريقية ويجعلها ولاية مستقلة ويولى عليها معاوية بن حديج السّكونى سنة ٤٥ للهجرة، ويولّى بدوره رويفع بن ثابت الأنصارى على طرابلس، ويترك معه كتيبة، ويدور عام وقيل بل عامان ويفتح رويفع جزيرة جربة شرقى مدينة قابس. حتى إذا كانت سنة ٥٠ للهجرة ولّى معاوية على المغرب جميعه عقبة بن نافع، فرأى بثاقب بصيرته أن يتخذ للجيش العربى قاعدة تكون معسكرا له، فيها ينزل الجيش ويسكنها ويخرج منها لمتابعة الفتوح فى المغرب، واختار موقعا فى داخل إفريقية التونسية غربى ميناء سوسة على بعد نحو ثلاثين ميلا من البحر المتوسط، وشيد فيه مدينته وسماها القيروان أى المعسكر، وجعل حولها سورا من القرميد، وشيّد فيها جامعا كبيرا، وسرعان ما استحالت القيروان مدينة ضخمة واستحال جامعها جامعة كبرى، ويعيد عقبة إلى إفريقية الهدوء والاستقرار ويقضى على الحكم البيزنطى فى الشمال الإفريقى جميعه. وبمجرد إتمامه لمدينته سنة ٥٥ للهجرة عزل، وتولّى المغرب أبو المهاجر، وقد نازل قبيلة أوربة من البرانس وزعيمها كسيلة فى تلمسان ودارت عليها الدوائر، وأسر كسيلة ودخل فى الإسلام. وتولّى الخلافة يزيد بعد أبيه معاوية، فأعاد إلى المغرب عقبة بن نافع سنة ٦٢ للهجرة، فسار بجيش ضخم اخترق به الجزائر والمغرب الأقصى حتى بلغ المحيط الأطلسى، وكان قد وبّخ كسيلة زعيم أوربة لما كان من حربه للمسلمين فأسرّها فى نفسه، وصمم على الانتقام، وفى عودة عقبة بالجيش تأخر عنه فى كتيبة صغيرة بجبال الأوراس جنوبى مدينة بسكرة فى الجزائر وكان كسيلة قد جمع من أنصاره جمعا كبيرا، فانتهز الفرصة وهجم على عقبة وصحبه واستشهد البطل العظيم، وأقيم له مسجد ضمّ رفاته، وسميت المنطقة باسمه: سيدى عقبة.