
Embora os árabes não tivessem avançado além da Cirenaica desde a década de 640, exceto em ataques periódicos, as expedições contra o norte da África bizantina foram renovadas durante o reinado de Mu'awiya.
Em 665 ou 666, Ibn Hudayj liderou um exército que atacou Bizacena (distrito do sul da África bizantina) e Gabes e capturou temporariamente Bizerte antes de se retirar para oEgito . No ano seguinte, Mu'awiya despachou Fadala e Ruwayfi ibn Thabit para atacar a ilha comercialmente valiosa de Djerba. Enquanto isso, em 662 ou 667, Uqba ibn Nafi, um comandante coraixita que desempenhou um papel fundamental na captura da Cirenaica pelos árabes em 641 , reafirmou a influência muçulmana na região de Fezzan, capturando o oásis Zawila e a capital Garamantes de Germa. Ele pode ter invadido o sul até Kawar, no atual Níger.