After the withdrawal of the Byzantines from Egypt, the Exarchate of Africa declared its independence. Under its exarch, Gregory the Patrician, its dominions extended from the borders of Egypt to Morocco. Abdullah ibn Sa'ad sent raiding parties to the west, resulting in considerable booty and encouraging Sa'ad to propose a campaign to conquer the Exarchate.

Uthman gave him permission after considering it in the Majlis al-Shura. A force of 10,000 soldiers was sent as reinforcement. The Rashidun army assembled in Barqa in Cyrenaica, and from there they marched west, captured Tripoli, and then advanced to Sufetula, Gregory's capital. In the Battle of Sufetula, the Exarchate was defeated and Gregory was killed due to the superior tactics of Abdullah ibn Zubayr. Afterward, the people of North Africa sued for peace, agreeing to pay an annual tribute. Instead of annexing North Africa, the Muslims preferred to make North Africa a vassal state. When the stipulated amount of the tribute was paid, the Muslim forces withdrew to Barqa. Following the First Fitna, the first Islamic civil war, Muslim forces withdrew from north Africa to Egypt. The Umayyad Caliphate would later re-invade North Africa in 664.