Завоевание Северной Африки, вероятно, стало естественным продолжением завоевания Египта. Все сведения, которыми мы располагаем о первых походах, исходят от единственного египетского хрониста Ибн Абд аль-Хакама, повествование которого использовалось в позднейших источниках. Возможно, летом 642 года, очень скоро после падения Александрии, Амр повел свое войско на запад. Путь, очевидно, оказался нетрудным, и армия быстро, не встречая сопротивления, достигла Барки. Византийский гарнизон и несколько местных землевладельцев отступил перед арабами к береговому порту Токра (древней Тавхире), откуда позже ушли в море. Большую часть городского населения, кажется, составляли берберы левафы, и именно с ними, а не с имперскими властями Амр заключил мир в обмен на выплату дани в 13 000 динаров. Рассказывали, что договор включал довольно оригинальную статью о том, что для сбора денег люди вправе продавать в рабство своих сыновей и дочерей. Возможно, это было началом массового обращения берберов в рабство, характерного для I века мусульманского правления в Северной Африке. Условлено было также, что ни один мусульманский сборщик налогов не вступит на эти земли и что люди Барки сами доставят собранную дань в Египет.
Затем Амр провел свое войско в обход залива Сирт, пройдя мимо Токры к Триполи. Здесь он натолкнулся на более серьезное сопротивление. Византийский гарнизон продержался целый месяц. Ибн Абд аль-Хакам описывает окончание осады в эпизоде, которыми арабы оживляют повествование, не претендуя на достоверность. Рассказ гласит, что один из арабов, осаждавших город, выехал на охоту с семерыми спутниками. Они обогнули город с запада и, оторвавшись от своего войска, утомленные жарой, решили вернуться к берегу. Между тем городская стена выходила к самому морю, и римские корабли стояли на якоре под самой стеной. Арабы заметили, что море немного отступило от стен, так что между водой и стеной образовался проход. По нему они подобрались к главной церкви и подняли там крик: «Аллах акбар!» Ромеи в панике бросились по своим кораблям, захватив все, что успели собрать, подняли паруса и бежали. Амр, видя этот переполох, ввел свои войска в город, который затем разграбили. На этой стадии не упоминается о его оккупации арабами, и, возможно, город после ухода арабов вернулся под власть Византии.
Амр вскоре двинулся дальше, повел своих людей на запад к Сабаре (Сабрате). Местные жители, решив, что Амр далеко и занят осадой Триполи, забыли об обороне. Город легко взяли и разграбили. Скоро и Лептис Магна (Лабла) попал в руки арабов. Затем Амр возвратился в Египет, несомненно, вполне удовлетворенный трофеями, взятыми им и его спутниками. Следы своего присутствия он оставил лишь в Барке, где установил налоги и назначил управляющего, Укбу ибн Нафи, которому предстояло стать героем завоевания мусульманами Северной Африки, и чье имя, подобно имени Халида ибн аль-Валида в Ираке и Сирии, вошло в историю и легенды как образец умелого и бесстрашного военачальника.
Смещение Амра с поста наместника Египта в 645 году привело к перерыву в военных действиях арабов. Продлился он не долго. В 647 году халиф Усман послал в Египет новую армию для помощи в африканской кампании. Список подразделений этой армии предполагает, что она насчитывала от 5000 до 10 000 человек, набранных большей частью, как и большинство арабов, воевавших в Египте, из южноаравийских племен. Командовал ими новый наместник Египта Абдаллах ибн Саад ибн Аби Сарх. Армия быстро двинулась вдоль побережья Северной Африки по землям, которые принадлежат теперь Тунису. Они, по-видимому, не стали тратить времени на повторный захват Триполи. Силами Византии в этом районе командовал экзарх Африки Григорий. Он, кажется, принял решение базироваться не в традиционной столице — Карфагене, а в Сбейтле, располагавшейся на юге Туниса. Возможно, там он предполагал встретиться с берберскими союзниками для более действенного отпора захватчикам. Две армии встретились вне стен города. Византийцы были разбиты наголову и, если верить арабским источникам, Григорий погиб в бою, хотя, по сведениям Феофана и других христианских авторов, он спасся и позже получил награду от императора.
Это сражение было единственным столкновением, которое произошло между арабами и византийцами в Северной Африке. Интересно отметить, что Григорий не пытался воспользоваться построенными в этих местах византийскими крепостями, а предпочел встретить врага в чистом поле. После его поражения остатки имперской армии, кажется, оттянулись в Карфаген, предоставив сражаться за контроль над страной арабам и берберам.
Добычу захватили огромную, и арабские источники, как обычно, уделяют куда больше места ее описанию и рассказу о дележе, чем всей остальной кампании. (Для примера: всадники получили по 3000 золотых динаров — 1500 на коня, и 1500 на человека, а пешие воины получили по 1500 динаров). После этого арабские войска почти двадцать лет не делали серьезных попыток упрочиться в Северной Африке. Возможно, что в этот период Барка и Киренаика оставались под властью мусульман, но, по всей видимости, тем экспансия и ограничилась. Арабо-египетские военачальники с египетскими войсками совершали периодические рейды в Триполитанию и Феццан, но армии, захватив добычу, неизменно возвращались.
За этот длительный период, кажется, только Укба ибн Нафи задумывался о более серьезных предприятиях. В центральном Алжире, там, где северные горы постепенно понижаются к краю Сахары, лежит маленький городок, построенный вокруг древнего святилища Сиди Окба и до сих пор посещаемый паломниками, надеющимися заслужить «барака» (благословение) от близости к великому святому. Термин «Сиди» происходит от классического арабского «сай-иди», что означает— мой господин: от того же арабского слово образован титул кастильского героя Эль Сида. Окба — это Укба ибн Нафи аль Фири, человек, который согласно историческим хроникам и популярному представлению принес в Магриб закон ислама. Он — единственный из первых мусульманских военачальников, чьей могиле оказаны такие почести. Кроме того, он мог претендовать на статус спутника Пророка, хотя только в том смысле, что, будучи маленьким мальчиком, он видел Мухаммада. Это еще увеличило его престиж в глазах потомков.
Укба, родившийся в Мекке под конец жизни Мухаммада, происходил из одного с ним племени — курайш, но из другой подгруппы — фир. Его предки относились к городской знати Мекки. Такое происхождение типично для людей, образовавших элиту раннего исламского государства и возглавивших его армии. Укба был единственный из спутников, сыгравших важную роль в завоевании Алжира и Марокко, и о нем можно сказать, что он принес «барака» самого Пророка в эту часть Северной Африки. Кроме того, он был единственным из сражавшихся здесь курайшитов, что еще упрочило его статус и репутацию. Одним словом, Укба стал мучеником, после того как он со своим маленьким отрядом повстречался в 683 году с намного превосходящим их войском берберов и был убит в сражении.
Укба приписывал свое возвышение тому обстоятельству, что его дядя по материнской линии был не кто иной, как сам Амр ибн аль-Ас, завоеватель Египта. Естественно, Амр доверял своему способному и честолюбивому племяннику важные поручения. Укба рано обнаружил свою страсть к экспедициям. Он участвовал в первой кампании Амра в Киренаике и проявил себя, возглавив рейд на оазис Зувай-ла к югу от Триполи. Нам рассказывают, что он дошел до самого Г^дамиса в глубине Ливийской пустыни и, что, возможно, важнее, завязал отношения с берберами левафами в районе Триполи. По словам арабского географа Йакута, Укба оставался в областях Барка и Зувайла, придя с дядей Амром ибн аль-Асом, и он собрал вокруг себя берберов, которых обратил в ислам.
В 670 году халиф Муавийя назначил Укбу правителем земель в Северной Африке, находившихся под властью мусульман, подчинив его наместнику Египта. Он решил открыть кампанию по завоеванию Ифрикии (более или менее совпадающей по территории с современным Тунисом) и утвердить там власть мусульман. Укба, хорошо знакомый с местными условиями, должен был понимать, какой это удачный момент для удара. Византийская администрация слабела день ото дня. Арабы атаковали Константинополь, и для его защиты требовались все силы империи. Не менее опасен был очередной внутренний раскол во власти империи. Императору Константину IV (668-685) бросил вызов претендент на трон из Сицилии, куда императору и пришлось ввести войска, чтобы справиться с ним. Однако настоящую угрозу представляли не ромеи: гораздо существенней было покорить берберов или договориться с ними.