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