Although the Arabs had not advanced beyond Cyrenaica since the 640s other than periodic raids, the expeditions against Byzantine North Africa were renewed during Mu'awiya's reign.

In 665 or 666 Ibn Hudayj led an army which raided Byzacena (southern district of Byzantine Africa) and Gabes and temporarily captured Bizerte before withdrawing to Egypt. The following year Mu'awiya dispatched Fadala and Ruwayfi ibn Thabit to raid the commercially valuable island of Djerba.Meanwhile, in 662 or 667, Uqba ibn Nafi, a Qurayshite commander who had played a key role in the Arabs' capture of Cyrenaica in 641, reasserted Muslim influence in the Fezzan region, capturing the Zawila oasis and the Garamantes capital of Germa. He may have raided as far south as Kawar in modern-day Niger.