Praetorian prefecture of Africa

In 533, the Roman army under Belisarius defeated and destroyed the Vandal Kingdom that had existed in the former Roman territories of Northern Africa. Immediately after the victory, in April 534, the emperor Justinian published a law concerning the administrative organization of the recovered territories. The old provinces of the Roman Diocese of Africa had been mostly preserved by the Vandals, but large parts, including almost all of Mauretania Tingitana, much of Mauretania Caesariensis and Mauretania Sitifensis and large parts of the interior of Numidia and Byzacena, had been lost to the inroads of Berber tribes, collectively called the Mauri (Moors). Nevertheless, Justinian restored the old administrative division, but raised the overall governor at Carthage to the supreme administrative rank of praetorian prefect, thereby ending the Diocese of Africa's traditional subordination to the Prefecture of Italy (then still under the rule of the Ostrogothic Kingdom). Seven provinces – four consular, three praesides – were designated:

From the aforesaid city, with the aid of God, seven provinces with their judges shall be controlled, of which Tingi, Carthage, Byzacium, and Tripoli, formerly under the jurisdiction of proconsuls, shall have consular rulers; while the others, that is to say, Numidia, Mauritania, and Sardinia shall, with the aid of God, be subject to governors.

— Codex Iustinianus, I.XXVII

It should be assumed that Mauretania Tingitana, traditionally part of the Diocese of Spain (then under the rule of the Visigothic Kingdom), was temporarily extinguished as a separate province in Justinian's arrangement and merged with Mauretania Caesariensis to form the province ruled from Tingi, and that "Mauretania" refers to Mauretania Sitifensis.[1] It is also noteworthy that the island of Sardinia was part of Africa rather than Italy.

Justinian's intent was to, in the words of the historian J.B. Bury, "wipe out all traces of the Vandal conquest, as if it had never been".[2] The churches were restored to the Chalcedonian clergy, and the remaining Arians suffered persecution. Even the land ownership was reverted to the status prior to the Vandalic conquest, but the scarcity of valid property titles after 100 years of Vandal rule created an administrative and judicial chaos.

The military administration was headed by the new post of magister militum Africae, with a subordinate magister peditum and four regional frontier commands (Leptis Magna for Tripolitania, Capsa or Thelepte for Byzacena, Cirta for Numidia, and Caesarea for Mauretania[3]) under duces. This organization was only gradually established, as the Romans pushed the Mauri back and regained these territories.[4]

When the Romans landed in Africa, the Moors maintained a neutral stance, but after the quick Roman victories, most of their tribes pledged loyalty to the Empire. The most significant tribes were the Leuathae in Tripolitania, and the Frexi in Byzacena. The Frexi and their allies were led by Antalas, while other tribes in the area followed Cutzinas. The Aurasii (the tribes of the Aurès Mountains) in Numidia were ruled by Iaudas, and the Mauretanian Moors were led by Mastigas and Masuna.[5]

After Belisarius departed for Constantinople, he was succeeded as magister militum Africae by his domesticus (senior aide), the eunuch Solomon from Dara. The tribes of Mauri living in Byzacena and Numidia almost immediately rose up, and Solomon set out with his forces, which included allied Moorish tribes, against them. The situation was so critical that Solomon was also entrusted with civil authority, replacing the first prefect, Archelaus, in the autumn of 534. Solomon was able to defeat the Mauri of Byzacena at Mamma, and again, decisively, at the battle of Mt. Bourgaon in early 535. In the summer, he campaigned against Iaudas and the Aurasii, who were ravaging Numidia, but failed to achieve any result. Solomon then set about erecting forts along the borders and the main roads, hoping to contain the raids of the Moors.

Africa, with the provinces of Byzacena, Zeugitana and Numidia.

In the Easter of 536 however, a large-scale military revolt broke out, caused by dissatisfaction of the soldiers with Solomon. Solomon, together with Procopius, who worked as his secretary, was able to escape to Sicily, which had just been conquered by Belisarius. Solomon's lieutenants Martinus and Theodore were left behind, the first to try to reach the troops at Numidia, and the second to hold Carthage.[6] Upon hearing about the mutiny, Belisarius, with Solomon and 100 picked men, set sail for Africa. Carthage was being besieged by 9,000 rebels, including many Vandals, under a certain Stotzas. Theodore was contemplating capitulation, when Belisarius appeared. The news of the famous general's arrival were sufficient for the rebels to abandon the siege and withdraw westwards. Belisarius, although able to muster only 2,000 men, immediately gave pursuit and caught up and defeated the rebel forces at Membresa. The bulk of the rebels however was able to flee, and continued to march towards Numidia, where the local troops decided to join them.[7] Belisarius himself was forced to return to Italy, and Justinian appointed his cousin Germanus as magister militum to deal with the crisis.

Germanus managed to win over many of the rebels to his side by appearing conciliatory and paying their arrears. Eventually, in the spring of 537, the two armies clashed at Scalae Veteres, resulting in a hard-won victory for Germanus. Stotzas fled to the tribesmen of Mauretania, and Germanus spent the next two years in re-establishing discipline in the army. Finally, Justinian judged the situation to have been stabilized enough, and in 539 Germanus was replaced by Solomon. Solomon carried on Germanus' work by pruning out of the army those of suspect loyalties and strengthening the network of fortifications. This careful organization enabled him to strike successfully against the Aurasii, evicting them from their mountain strongholds, and firmly establish Roman rule in Numidia and Mauretania Sitifensis.[8]

Africa enjoyed peace and prosperity for the next few years, until the arrival of the great plague c. 542, during which the people of the province suffered greatly. At the same time, the arrogant behaviour of some Roman governors alienated the Mauri leaders, such as Antalas at Byzacena, and provoked them to rise up and raid Roman territory. So it was that during a battle with the Mauri at Cillium in Byzacena in 544, the Romans were defeated and Solomon himself killed.[9][10] Solomon was succeeded by his nephew, Sergius, who as dux of Tripolitania had been largely responsible for the Moorish uprising. Sergius was both unpopular and of limited abilities, while the Mauri, joined by the renegade Stotzas, gathered together under the leadership of Antalas.[11] The Moors, aided by Stotzas, were able to enter and sack the coastal city of Hadrumetum by trickery. A priest named Paulus was able to retake the city with a small force without help from Sergius, who refused to march forth against the Moors. Despite this setback, the rebels roamed the provinces at will, while the rural population fled to the fortified cities and to Sicily.[12]

Justinian then sent Areobindus, a man of senatorial rank and husband to his niece Praejecta, but otherwise undistinguished, with a few men to Africa, not to replace Sergius, but to share command with him. Sergius was entrusted with the war in Numidia, while Areobindus undertook to subdue Byzacena. Areobindus sent out a force under the able general John against Antalas and Stotzas. Because Sergius did not come to their aid as requested, the Romans were routed at Thacia, but not before John mortally wounded Stotzas in single combat. The effects of this disaster at least forced Justinian to recall Sergius and restore unity of command in the hands of Areobindus.[13] Soon after, in March 546, Areobindus was overthrown and murdered by Guntharic, the dux Numidiae, who had come into negotiations with the Moors and intended to set himself up as an independent king. Guntharic himself was overthrown by loyal troops under the Armenian Artabanes in early May. Artabanes was elevated to the office of magister militum Africae, but was soon recalled to Constantinople.[14]

The man Justinian sent to replace him was the talented general John Troglita, whose exploits are celebrated in the epic poem Iohannis, written by Flavius Cresconius Corippus. Troglita had already served in Africa under Belisarius and Solomon, and had a distinguished career in the East, where he had been appointed dux Mesopotamiae. Despite his numerically weak forces, he managed to win over several Moorish tribes, and in early 547 he decisively defeated Antalas and his allies, and drove them from Byzacena. As Procopius recounts:

And this John, immediately upon arriving in Libya, had an engagement with Antalas and the Moors in Byzacium, and conquering them in battle, slew many; and he wrested from these barbarians all the standards of Solomon, and sent them to the emperor—standards which they had previously secured as plunder, when Solomon had been taken from the world.

— Procopius, De Bello Vandalico II.XXVIII

A few months later, however, the tribe of the Leuathae, in Tripolitania, rose up, and inflicted a severe defeat upon the imperial forces in the plain of Gallica. The Leuathae were joined by Antalas, and the Moors once again raided freely as far as Carthage.[15] Early in the next year John mustered his forces, and together by several allied Moorish tribes, including the former rebel Cutzinas, utterly defeated the Moors at the battle of the Fields of Cato, killing seventeen of their leaders and putting an end to the revolt that had plagued Africa for almost 15 years.

The famous Lady of Carthage mosaic, possibly a portrait of Theodora, one of the major surviving pieces of Byzantine art in modern Tunisia

For the next decades, Africa remained tranquil, allowing it to recover. Peace might not have lasted as long, had not Troglita perceived that the complete eviction of the Mauri from the interior of the provinces, and the complete restoration of the province to its ancient bounds was impossible. Instead, he opted to accommodate himself with the Moors, promising them autonomy in exchange for becoming the Empire's foederati.[16] The loyalty of these dependent princes of the various Moorish tribes was secured by means of annual pensions and gifts, and the peace was kept by a strong network of fortifications, many of which still survive to the present day.

The only interruption to the province's tranquility was a brief Moorish revolt of 563. It was caused by the unwarranted murder of the aged tribal leader Cutzinas, when he came to Carthage to receive his annual pension, by the magister militum, John Rogathinus. His sons and dependants rose up, until an expeditionary force under the tribune Marcian, nephew of the Emperor, succeeded in restoring the peace.[17]

During the reign of Justin II (565–578), great care was shown to Africa. Under the prefect Thomas, during the period 565–570 the network of fortifications was further strengthened and expanded, the administration reformed and decentralized, and largely successful efforts were made to proselytize the Garamantes of the Fezzan and the Gaetuli, living to the south of Mauretania Caesariensis.[18] At the same time, Africa was one of the more tranquil regions of the Empire – which was being assaulted on all sides – and this allowed for troops to be transferred from the province to the East.[19]

In Mauretania, between the Roman outpost of Septum and the province of Caesariensis, various small Moorish kingdoms, which also ruled over Romanized urban populations, had been established ever since the arrival of the Vandals. Little information exists about them, but these were never subdued by the Vandals, and claimed continuity from the Roman Empire, their leaders styling themselves with titles such as imperator, like the chieftain Masties at Arris (in the Aures) in the late 5th century, or, in the case of king Masuna of Altava (modern Ouled Mimoun, northwest Algeria), rex gentium Maurorum et Romanorum in the early 6th century.[20]

When Belisarius defeated the Vandals, the Romano-Moorish kings had apparently acknowledged Roman suzerainty (at least nominally), but soon, taking advantage of the Moorish revolts, renounced it. In the late 560s, the Moorish king Garmul (probably a successor of the aforementioned Masuna of Altava) launched raids into Roman territory, and although he failed to take any significant town, three successive generals (the praetorian prefect Theodore and the magister militum Theoctistus in 570, and Theoctistus' successor Amabilis in 571) are recorded by John of Biclaro to have been killed by Garmul's forces.[21] His activities, especially when regarded together with the simultaneous Visigoth attacks in Spania, presented a clear threat to the province's authorities. Garmul was not the leader of a mere semi-nomadic tribe, but of a fully-fledged barbarian kingdom, with a standing army. Thus the new emperor, Tiberius II Constantine, re-appointed Thomas as praetorian prefect, and the able general Gennadius was posted as magister militum with the clear aim of reducing Garmul's kingdom. Preparations were lengthy and careful, but the campaign itself, launched in 577–78, was brief and effective, with Gennadius utilizing terror tactics against Garmul's subjects. Garmul was defeated and killed by 579, and the coastal corridor between Tingitana and Caesariensis secured.[22]

Gennadius remained in Africa as magister militum for a long time (until the early 590s), and it was he who became the first exarchus of Africa,[23][24] when Emperor Maurice established the exarchate in the late 580s, uniting civil and military authority in his hands. The exarchate extended over North Africa, the imperial possessions in Spain, the Balearic Islands, Sardinia, and Corsica. It prospered greatly, and under Heraclius, African forces overthrew the tyrant Phocas in 610. The exarchate was a practically autonomous entity from the 640s on, and survived until the fall of Carthage to the Muslims in 698.