Однако подавляющее большинство населения составляли берберы. Имя «берберы» происходит, конечно, от термина «варвары» (иноземцы), который в Римской империи применяли к другим народам и который перешел в арабский в звучании «бербер». Земли, населенные берберами, простирались от края долины Нила до самого Марокко. Берберы не образовывали никакого политического единства и принадлежали к множеству разных племен, но их объединяла общность языка, или языковой семьи, совершенно отличной как от латыни, так и от арабского. На этом языке до XII века редко записывали повествования или административные распоряжения, и бербер, желавший попасть в правительственные чиновники или получить образование, вынужден был выучить латынь или греческий— в римскую и ромейскую эпоху, или арабский — после мусульманского завоевания.
Общество берберов можно назвать племенным, но образ жизни разных племен сильно разнился. Некоторые, в основном в горных районах, жили родовыми селениями и занимались земледелием. Другие жили отгонным скотоводством, перегоняя стада летом — в горы, а зимой — в низины. Были и чистые кочевники, скитавшиеся по необозримым пространствам Северной Сахары. Классические источники приводят множество наименований берберских племен Северной Африки, и, несколькими веками позже, то же делают арабские источники. Даже учитывая различия в языке и письменности, трудно проследить реальные связи. Представляется, что с VI по VIII век среди берберов происходили большие изменения, при которых одни племенные группы исчезали, сменяясь другими. По-видимому, за столетие, предшествовавшее арабскому завоеванию, берберы сместились с востока к западу. Возможно, именно это обстоятельство отражают позднейшие арабские источники, утверждающие, что основная группа берберов при-шла с Аравийского полуострова или из Палестины. Реальных доказательств этого не существует: в самом деле, то, что язык берберов не принадлежал к семитской группе, указывает, что такое маловероятно, но здесь могла отразиться память о миграции на запад. Левафы в VI веке пришли из района Барки на запад, в Триполитанию, и в 543 году изгнали византийского наместника из Лептис Магны. За ними последовали хаввары — еще одна группа берберских племен, пришедших из Киренаики. Процесс тагхриба — продвижения на запад, определявший движение арабских племен в XI веке, по-видимому, следовал образцу переселения берберов VI и начала VII веков.
Завоевание Северной Африки, вероятно, стало естественным продолжением завоевания Египта. Все сведения, которыми мы располагаем о первых походах, исходят от единственного египетского хрониста Ибн Абд аль-Хакама, повествование которого использовалось в позднейших источниках. Возможно, летом 642 года, очень скоро после падения Александрии, Амр повел свое войско на запад. Путь, очевидно, оказался нетрудным, и армия быстро, не встречая сопротивления, достигла Барки. Византийский гарнизон и несколько местных землевладельцев отступил перед арабами к береговому порту Токра (древней Тавхире), откуда позже ушли в море. Большую часть городского населения, кажется, составляли берберы левафы, и именно с ними, а не с имперскими властями Амр заключил мир в обмен на выплату дани в 13 000 динаров. Рассказывали, что договор включал довольно оригинальную статью о том, что для сбора денег люди вправе продавать в рабство своих сыновей и дочерей. Возможно, это было началом массового обращения берберов в рабство, характерного для I века мусульманского правления в Северной Африке. Условлено было также, что ни один мусульманский сборщик налогов не вступит на эти земли и что люди Барки сами доставят собранную дань в Египет.
Затем Амр провел свое войско в обход залива Сирт, пройдя мимо Токры к Триполи. Здесь он натолкнулся на более серьезное сопротивление. Византийский гарнизон продержался целый месяц. Ибн Абд аль-Хакам описывает окончание осады в эпизоде, которыми арабы оживляют повествование, не претендуя на достоверность. Рассказ гласит, что один из арабов, осаждавших город, выехал на охоту с семерыми спутниками. Они обогнули город с запада и, оторвавшись от своего войска, утомленные жарой, решили вернуться к берегу. Между тем городская стена выходила к самому морю, и римские корабли стояли на якоре под самой стеной. Арабы заметили, что море немного отступило от стен, так что между водой и стеной образовался проход. По нему они подобрались к главной церкви и подняли там крик: «Аллах акбар!» Ромеи в панике бросились по своим кораблям, захватив все, что успели собрать, подняли паруса и бежали. Амр, видя этот переполох, ввел свои войска в город, который затем разграбили. На этой стадии не упоминается о его оккупации арабами, и, возможно, город после ухода арабов вернулся под власть Византии.