تربطه بعمرو بن العاص صلة قرابة، فقد كانا ابنيْ خالة. وتذكر مصادر أخرى أن عقبة «هو ابن أخي العاص بن وائل السهمي لأمه» [2] . هبط مع أهله إلى مصر وسكنوا زُقاق القناديل بالقاهرة، وكانت دارهم تعرف بدار الفهريين. الأخبار الأولى التي نلقاها في المصادر التاريخية تتحدث عن عقبة بن نافع تُخبرنا بأنه كان في جُند عمرو بن العاص لما فتح مصر عام 20هـ [3] . ثم بدأ يقوم ببعض الدوريات الاستطلاعية إلى أرض النُّوبَة، ثم بعد قليل تمكّن عقبة من فتح زوِيلَة وبَرْقَة ولم يرجع إلى مصر حتى أسلم أهلهما كلهم. وبعد أن فتح عمرو بن العاص مدينة طرابلس، غزا عُقبة بن نافع الفهري إفريقية سنة 41هـ، لكنه لم يفتحها. وفي السنوات التالية فتح لُوَاتَة، ومَزَاتَة، وغدامس، وبعض كُوَرِ السُّودان، ووَدّان، وعامّة بلاد البربر. ولمّا وُلي مُعاوية ابن أبي سفيان الخلافة وجّه عقبة بن نافع الفهري إلى إفريقية غازيا في عشرة آلاف من المسلمين، فافتتحها، واختطّ قيروانها [4] .

وقد امتدت ولاية عقبة بن نافع الأولى على إفريقية من عام 50هـ إلى 54هـ، وفيها بنى مدينة القيروان، وقد كان موضعها غَيْضَة ذات طَرْفَاء وشجر لا يُرَام من السباع والحيات والعقارب القتّالة. يذكر ابن الأثير أن عُقبة بن نافع «ركب بالناس إلى موضع القيروان اليوم، وكان غيْضة كثيرة الأشجار مأوى الوُحُوش والحيّات، فأمر بقطع ذلك وإحراقه، واختطَّ المدينة، وأمر الناس بالبنيان» [5] .