The Exarchate of Africa was in internal turmoil due to the conflict between the mainly Orthodox Chalcedonian population and the supporters of Monotheletism, an attempt at compromise between Chalcedonianism and Monophysitism devised and promoted by Emperor Heraclius in 638. In 642–643, the Arabs had seized Cyrenaica and the eastern half of Tripolitania, along with Tripoli. It was only an order from Caliph Umar that halted their westward expansion. In 646, the exarchGregory the Patrician launched a rebellion against Emperor Constans II. The obvious reason was the latter's support for Monotheletism, but it undoubtedly was also a reaction to the Muslim conquest of Egypt, and the threat it presented to Byzantine Africa. The revolt seems to have found broad support among the populace as well, not only among the Romanized Africans, but also among the Berbers of the provincial hinterland.
Battle
In 647, Umar's successor Uthman ordered Abdallah ibn Sa'ad to invade the Exarchate with 20,000 men. The Muslims invaded western Tripolitania and advanced up to the northern boundary of the Byzantine province of Byzacena. Gregory confronted the Arabs on their return at Sufetula, but was defeated and killed. Agapius of Hierapolis and some Syriac sources claim that he survived the defeat and fled to Constantinople, where he was reconciled with Constans, but most modern scholarsaccept the Arab chroniclers' account of his death in battle. The Arab accounts also claim that the Muslims capturedGregory's daughter, who had fought at her father's side. She was carried back to Egypt as part of the booty, but she fell from her camel on the march and was killed.
Aftermath
After Gregory's death, the Arabs sacked Sufetula and raided across the Exarchate, while the Byzantines withdrew to their fortresses. Unable to storm the Byzantine fortifications, and satisfied with the huge amounts of plunder they had made, the Arabs agreed to depart in exchange for the payment of a heavy tribute in gold. Despite the fact that the Arab raid was not followed up for some time, and the restoration of ties with Constantinople, Byzantine rule over Africa was shaken to its roots by Gregory's rebellion and the Arab victory. The Berber tribes in particular shook off their allegiance to the Empire, and most of southern Tunisia seems to have slipped outside the control of Carthage. Thus the Battle of Sufetula marked "the end, more or less near, but inevitable, of Byzantine domination in Africa".