Den
muslimske erobring af Nordafrika, som havde opslugt Tripoli i 655, stødte
videre vestpå under Okba (Oqba). I 670 grundlagde han Kairouan,
som senere blev en hellig by i Islam, og angreb derpå så langt
vestpå som til Tangier, idet han gik uden om det nordlige Tunesien.
Okba, nevø til erobreren af Egypten Amr ibn-al-As, blev dræbt
på tilbagemarchen i 683 (og hævet til helgen af araberne).
Hans efterfølger, Hasan ibn No'man, konsoliderede erobringen ved
at angribe de tunesiske byer Utica og Kartago, det Byzantinske Riges
sidste udposter i Afrika. Hasans hårdt ridende kavalerister brød
ind i Utica, ødelagde den og rykkede derpå 24 km mod sydøst
til Kartago. Her smuldrede den byzantinske garnison igen overfor et voldsomt
arabisk stormløb. Den gamle by blev reduceret til status som en
ubetydelig landsby.
De berberiske stammefolk, som havde modstået araberne
mere effektivt end byzantinerne, accepterede fred nogle få år
efter. Hele Nordafrika kom nu under muslimsk styre.