Халиф назначил командующим Хассана ибн аль-Нумана аль-Гассани. Хассан происходил из рода Гассанидов, возглавлявшего арабов Сирийской пустыни в столетие, пред-шествовавшее мусульманскому завоеванию. Некоторые члены этого рода перебрались через границу иммигрировав в Византийскую империю, но другие остались в Сирии и вошли в состав Омейядской элиты наряду с теми сирийскими арабами, которые составляли становой хребет режима. Он получил титул «шейх амин» — верный старец. Он показал себя способным военачальником и надежным администратором и во многих отношениях может считаться истинным основателем мусульманской Северной Африки. Халиф дал ему войско в 40 000 человек — самую большую из мусульманских армий, появлявшихся в этих местах. Экспедиция предстояла серьезная.

Добравшись до Ифрикии после долгого марша вдоль побережья Северной Африки, Хассан избрал первой целью своей атаки Карфаген, последний центр ромейской администрации этого района. Можно удивляться тому что мусульмане не атаковали этого города прежде. Самое правдоподобное объяснение столь очевидному упущению состоит в том, что в берберах они видели куда более грозного врага, с которым необходимо было справиться или добиться мира. Византийцев, загнанных за стены их города, оставили в покое. Но недавняя высадка с моря на Киренаику показала, что те все еще представляют угрозу, и Хассан решил покончить с ней раз и навсегда.

Падение Карфагена — крупное событие, потому что оно обозначило окончательное и безвозвратное окончание римского владычества над Северной Африкой. В военном отношении это была скорее мирная оккупация, нежели крупная осада. Город, стоящий на чудесном участке побережья над Тунисским заливом, восемьсот лет был оплотом римской власти. Некогда его украшали множество монументальных зданий, а в период поздней античности к ним добавились величественные церкви. Во II веке н. э. в нем насчитывали полмиллиона жителей, а Антониновы бани, фрагменты которых можно видеть и теперь, были величайшими в римском мире. Арабский хронист Ибн Идари говорит, что в его дни (XIII в.) город еще выделялся внушительными развалинами, свидетельствовавшими о его славном прошлом. Он добавляет, что жители окрестностей Туниса, точь-в-точь как современные туристы, до сих пор приезжают туда, чтобы подивиться чудесам и монументам, устоявшим перед напором времени. Карфаген 698 года был лишь тенью великого города, существовавшего задолго до завоевания его римлянами. По словам Ибн Абд аль-Хакама, в нем жила лишь горстка жалких обитателей. Город, очевидно, был в основном покинут, и в нем уже полвека не строили значительных зданий. С гибелью средиземноморской торговли город утратил основу своего существования, и теперь в громадных руинах остались лишь несколько горожан да крошечный гарнизон.

Не удивительно, что город почти не сопротивлялся. По некоторым источникам, жители сразу собрали свои пожитки и ночью отчалили на судах, так что арабская армия вошла уже в пустой город. Мы не имеем сообщений о правильной осаде и о захваченной добыче: еще одно подтверждение того, что город мог быть покинут еще до завоевания. Мусульмане, утвердив свою власть, не пытались поставить в городе гарнизон или возвести мечеть. В сущности, центр населенности переместился от прибрежного Карфагена в материковый Кайруан, как в Египте — из Александрии в Фустат.

Падение Карфагена обозначило окончание римского присутствия в Северной Африке, однако многие берберские племена оставались непокоренными. Главенство над их сопротивлением перешло теперь к таинственной фигуре Кахины (Пророчицы). Репутация этой берберской Будикки с ее длинными космами волос и экстатическими пророчествами на века сохранилась в истории и легендах как символ сопротивления завоеваниям мусульман и их нормам жизни. Современные культуры восславляют ее то как героиню женской эмансипации и силы, то как героиню сопротивления и независимости берберов, то как «иудейскую принцессу», не пожелавшую отречься от своей веры, то как великую африканскую царицу. Она, безусловно, принадлежала к племени берберов из обширного племени заната, но есть сведения, что она вышла замуж за византийца, а по религии была христианкой или иудейкой.

Традиционный взгляд на Кахину подытожил в XVIII веке Эдуард Гиббон, широта знаний которого не перестает удивлять. Он описывает, как произошло объединение «не знавших порядка» берберов.

Далее он описывает, какие меры приняла Кахина против возвращения арабов:

За легендой трудно различить реальность. Власть Кахины сосредоточилась в районе гор Ореса. Этот горный массив на западе Алжира в наивысшей точке достигает высоты 2300 м. Протяженность гор не более 100 километров с запада на восток, и 50 — с севера на юг. Севернее лежит плодородное плато, на юге горы резко опускаются к границе Сахары. Горы эти изрезанные и скалистые, а в глубоких ущельях прячутся затерянные деревушки и пальмовые рощи. Они представляли удобную стратегическую позицию. Всего один дневной переход отделал дикие и неприступные горы от равнин Туниса и центра власти арабов. Кроме того, массив господствовал над дорогой из Туниса к другим частям Алжира и Марокко. Не покорив или, по крайней мере, не примирив с собой Ореса, арабская армия не могла вести действий в этих районах. Горы представляли превосходную твердыню для тех, кто хотел сопротивляться пришельцам извне, и они всегда оказывались центром сопротивления для берберов: первый выстрел алжирского восстания против власти Франции в 1954 году прозвучал в Оресе.

Самый полный отчет о Кахине мы находим в труде Ибн Идари. Хассан, вступив в Кайруан, спросил, кто самый важный из царей, еще уцелевших в Ифрикии, и ему ответили, что это Кахина в горах Ореса, которой страшатся все ромеи и повинуются все берберы. Еще добавили, что если он ее убьет, весь Магриб будет в его руках. Хассан выступил против Кахины. Она раньше него добралась до города Багхаи, изгнала из него ромеев и уничтожила город, потому что боялась, что Хассан, захватив его, устроит там укрепленную базу. Он достиг гор и разбил лагерь в Вади Маскияна. Там и встретилась с ним Кахина. Его лагерь стоял в верховьях вади, а ее силы были расположены ниже. Однажды вечером всадники обеих сторон сошлись, но Хассан отказался в тот день начинать сражение, так что оба войска провели ночь в седлах. На следующий день войска сражались долго и жестоко, однако войска Хассана в конце концов обратились в бегство. Кахина погналась за ними, убив многих и взяв пленных. Она оттеснила Хассана за Габис. Кажется, он нашел убежище в Киренаике, откуда написал халифу с просьбой о подкреплении, объяснив в том же письме, что народы Магриба не имеют политической программы или цели, а подобны вольно пасущимся стадам. Халиф в ответе велел ему оставаться на месте. Дворцы, выстроенные Хассаном и его людьми близ Барки, были еще известны шесть веков спустя во времена Ибн Идари как «Кусур Хассан» — Дворцы Хассана.