After the final consolidation of Egypt, ʿUthman ﵁ appointed ʿAbdullah ibn Saʿd ibn Abi Sarh ﵁ in 27 AH to lead a campaign into Ifriqiya. The occasion was twofold: on the one hand, the dangers that the Byzantine exarch Gregorius, who had declared himself independent of Constantinople, posed to Egypt’s western frontier; on the other, the wealth of Africa Province, of which the Muslims had already received reports through Egyptian merchants.
Twenty thousand horsemen were assembled in Upper Egypt. The troops were mixed: Arab horsemen from the Hijaz, experienced in the Egyptian conquest; Egyptian cavalry, recruited in the garrisons of Fustat and Alexandria; and reinforcements from the Levant, sent by Muʿawiyah ﵁ at the khalifah’s request. ʿUthman ﵁ had explicitly instructed ʿAbdullah ﵁: if Gregorius submitted, peace; if he resisted, battle; and in either case no permanent occupation after the campaign, for the Muslim forces were needed elsewhere.
In Rajab 27 AH the main army departed from Aswan, westward through the Khargah oasis, then northward to Barqa (Cyrenaica). In Barqa the provisioning was completed: grain and water for the march ahead; local guides who knew the mountain passes and oases between Barqa and Tripolis; and reconnaissance sent forward. From Barqa the army marched through Cyrenaica, past Tripolis (which already fell under Muslim administration), and then inland toward Sufetula. The scouting parties brought in the first detailed reports of Gregorius’ concentrations at Sbeitla: a large army, but not yet fully mobilized.