Укба приписывал свое возвышение тому обстоятельству, что его дядя по материнской линии был не кто иной, как сам Амр ибн аль-Ас, завоеватель Египта. Естественно, Амр доверял своему способному и честолюбивому племяннику важные поручения. Укба рано обнаружил свою страсть к экспедициям. Он участвовал в первой кампании Амра в Киренаике и проявил себя, возглавив рейд на оазис Зувай-ла к югу от Триполи. Нам рассказывают, что он дошел до самого Г^дамиса в глубине Ливийской пустыни и, что, возможно, важнее, завязал отношения с берберами левафами в районе Триполи. По словам арабского географа Йакута, Укба оставался в областях Барка и Зувайла, придя с дядей Амром ибн аль-Асом, и он собрал вокруг себя берберов, которых обратил в ислам.
В 670 году халиф Муавийя назначил Укбу правителем земель в Северной Африке, находившихся под властью мусульман, подчинив его наместнику Египта. Он решил открыть кампанию по завоеванию Ифрикии (более или менее совпадающей по территории с современным Тунисом) и утвердить там власть мусульман. Укба, хорошо знакомый с местными условиями, должен был понимать, какой это удачный момент для удара. Византийская администрация слабела день ото дня. Арабы атаковали Константинополь, и для его защиты требовались все силы империи. Не менее опасен был очередной внутренний раскол во власти империи. Императору Константину IV (668-685) бросил вызов претендент на трон из Сицилии, куда императору и пришлось ввести войска, чтобы справиться с ним. Однако настоящую угрозу представляли не ромеи: гораздо существенней было покорить берберов или договориться с ними.
Укба прибыл в Северную Африку с войском, набранным в основном из арабов, поселившихся в Египте. Известно, что с ним было 10 000 всадников арабской конницы, и ее еще пополнили берберы, вероятно, в основном из племени левафов, уже обращенного в ислам. Первой целью Укбы было основать военную базу в сердце Ифрикии. История основания города Кайруан пересказывалась в XIII веке географом Иакутой по более древним источникам, не дошедшим до нас.