Na de definitieve consolidatie van Egypte stelde ʿUthman ﵁ in 27 AH ʿAbdullah ibn Saʿd ibn Abi Sarh ﵁ aan om een veldtocht naar Ifriqiya te leiden. De aanleiding was dubbel: enerzijds de gevaren die de Byzantijnse exarch Gregorius, die zich onafhankelijk van Constantinopel had verklaard, voor de Egyptische westgrens vormde; anderzijds de rijkdom van Africa Province, waarvan de moslims via Egyptische handelaren reeds berichten hadden ontvangen.
Twintigduizend ruiters werden in Boven-Egypte verzameld. De troepen waren gemengd: Arabische ruiters uit de Hijaz, ervaren in de Egyptische conquest; Egyptische cavalerie, geworven in de garnizoenen van Fustat en Alexandrië; en versterking uit de Levant, gestuurd door Muʿawiyah ﵁ op verzoek van de khalifah. ʿUthman ﵁ had ʿAbdullah ﵁ uitdrukkelijk geïnstrueerd: indien Gregorius zich onderwierp, vrede; indien hij weerstand bood, gevecht; en in beide gevallen geen vaste bezetting na de veldtocht, want de moslim-krachten waren elders nodig.
In Rajab 27 AH vertrok het hoofdleger uit Aswan, westwaarts door de Khargah-oase, dan noordwaarts naar Barqa (Cyrenaica). In Barqa werd de bevoorrading voltooid: graan en water voor de verdere mars; lokale gidsen die de bergpassen en oasen tussen Barqa en Tripolis kenden; en verkenning vooruit. Vanuit Barqa marcheerde het leger door Cyrenaica, langs Tripolis (dat reeds onder moslim-administratie viel), en daarna landinwaarts richting Sufetula. De verkenningstroepen brachten de eerste gedetailleerde rapporten in van Gregorius’ concentraties bij Sbeitla: een groot leger, maar nog niet volledig gemobiliseerd.