Background

In the Vandalic War of 533, Byzantine forces under Belisarius reconquered the Maghreb along with Corsica and Sardinia and the Balearic Islands. Emperor Justinian I (r. 527–565) organized the recovered territories as the Praetorian prefecture of Africa, which included the provinces of Africa Proconsularis, Byzacena, Tripolitania, Numidia, Mauretania Caesariensis and Mauretania Sitifensis, and was centered at Carthage. In the 550s, a Roman expedition succeeded in regaining parts of southern Spain, which were administered as the new province of Spania.

After the death of Justinian in 565, the Eastern Roman Empire came increasingly under attack on all fronts, and emperors often left the more remote provinces to themselves to cope as best they could for extended periods, although military officers, such as Heraclius the Elder (Exarch c. 598–610), continued to rotate between the eastern provinces and Africa. By the 640s and 650s, Byzantium had lost its province of Mesopotamia to the Muslims, who also extinguished the Byzantines' rival, the Sassanian Empire (651). Constantinople thereby lost an important source of experienced officers seasoned by constant border warfare with the Persians. The Heraclian dynasty (610-711) did continue to appoint some competent eastern officers to African posts, such as the Armenian Narseh, who commanded Tripoli, and John, the dux of Tigisis. Walter Kaegi speculates that some Armenian officers might have asked to transfer back to the east to defend their homes as the Muslims advanced into Armenia, but the sources are silent. Yet the officers who continued to arrive from the east after the loss of Mesopotamia would have been more accustomed to defeats like the Battle of Yarmouk (636) than the previously winning strategies used against the Sassanians, and new tactics and strategies developed slowly.^{[1]: 100–104}

Establishment of the Exarchate

The conquests of Justinian I overextended the resources of the Eastern Roman Empire, and led to the establishment of the Exarchates

The late Roman administrative system, as established by Diocletian, provided for a clear distinction between civil and military offices, primarily to lessen the possibility of rebellion by over-powerful provincial governors. Under Justinian I, the process was partially reversed for provinces that were judged to be especially vulnerable or in internal disorder. Capitalizing upon this precedent and taking it one step further, the emperor Maurice sometime between 585 and 590 created the office of exarch, which combined the supreme civil authority of a praetorian prefect and the military authority of a magister militum, and enjoyed considerable autonomy from Constantinople. Two exarchates were established, one in Italy, with its seat at Ravenna (hence known as the Exarchate of Ravenna), and one in Africa, based in Carthage and including all imperial possessions in the western Mediterranean. The first African exarch was the patricius Gennadius.^[2]: 273

Among the provincial changes, Tripolitania was detached from the province of Africa and placed under the province of Egypt,^[3]: 120 Mauretania Caesariensis and Mauretania Sitifensis were merged to form the new province of "Mauretania Prima", while Mauretania Tingitana, effectively reduced to the city of Septum (Ceuta), was combined with the citadels of the Spanish coast (Spania) and the Balearic Islands to form "Mauretania Secunda".^[2]: 273

The Visigothic Kingdom was a continuous threat to the exarchate. The African exarch was in possession of Mauretania II, which was little more than a tiny outpost in southern Spain. The conflict continued until the final conquest of the last Spanish strongholds in c. 624 by the Visigoths. The Byzantines retained only the fort of Septum (modern Ceuta), across the Strait of Gibraltar.

During the successful revolt of the exarch of Carthage, Heraclius the Elder, and his namesake son Heraclius in 608, the Berbers comprised a large portion of the fleet that transported Heraclius to Constantinople. Due to religious and political ambitions, the Exarch Gregory the Patrician (who was related by blood to the imperial family, through the emperor's cousin Nicetas) declared himself independent of Constantinople in 647. At this time the influence and power of the exarchate was exemplified in the forces gathered by Gregory in the battle of Sufetula also in that year where more than 100,000 men of Amazigh origin fought for Gregory.

The Arab Muslim conquest

In 647, the first Islamic expeditions began with an initiative from Egypt under the emir Amr ibn al-As and his nephew Uqba ibn Nafi. Sensing Roman weakness they conquered Barca, in Cyrenaica, then moved on to Tripolitania, where they encountered resistance.

Due to the unrest caused by theological disputes concerning Monothelitism and Monoenergism, the exarchate under Gregory the Patrician distanced itself from 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.