the empire in open revolt. The flood of refugees from Egypt (especially Melkites), Palestine, and Syria exacerbated religious tensions in Carthage and further raised the alarm to Gregory of the approaching Arab threat. Sensing that the more immediate danger came from the Muslim forces, Gregory gathered his allies and confronted the Muslims, but was defeated at the Battle of Sufetula, the new capital of the exarchate, since Gregory had moved to the interior for a better defense against Roman attacks from the sea. Afterwards, the exarchate became a semi-client state under a new exarch called Gennadius. Attempting to maintain tributary status with Constantinople and Damascus strained the resources of the exarchate and caused unrest amongst the population. The exarchate scored a major victory over the forces of Uqba ibn Nafi at the Battle of Vescera in 682, aided by the Berber king, Kusaila. This victory forced the Muslim forces to retreat to Egypt, giving the exarchate a decade's respite. However, the repeated confrontations took their toll on the dwindling and ever-divided resources of the exarchate. In 698, the Muslim commander Hasan ibn al-Nu'man and a force of 40,000 men crushed Carthage. Many of its defenders were Visigoths sent to defend the exarchate by Wittiza, who also feared Muslim expansion. Many Visigoths fought to the death; in the ensuing battle Carthage was again reduced to rubble, as it had been centuries earlier by the Romans. The loss of the mainland African exarchate was an enormous blow to the Byzantine Empire in the Western Mediterranean, because Carthage and Egypt were Constantinople's main sources of manpower and grain. The Byzantines never recovered their territories in Africa. Known and postulated Exarchs of Africa Notes References Further reading Byzantine North Africa History of Ceuta History of Tangier History of Gibraltar 7th century in the Visigothic Kingdom States and territories established in the 580s States and territories disestablished in the 7th century 698 disestablishments 580s establishments 6th-century establishments in the Byzantine Empire 7th-century disestablishments in Africa Maurice (emperor)