In the later division of the Roman Empire under the Emperor Diocletian, the eastern part of Mauretania Caesariensis, from Saldae to the river Ampsaga, was erected into a new province, and called Mauretania Sitifensis from the inland town of Setifis. At the time of Constantine the Great, Mauretania Sitifensis was assigned to the administrative Diocese of Africa, in the praetorian prefecture of Italy. The new province had a huge economic development in the IV century, until the conquest by the Vandals. In this province the DonatismChristian denomination challenged the Roman Church, that was the main local religion after Constantine, while Setifis was a center of Mithraism. While in certain areas under Vandal and Byzantine control, most of Mauretania Sitifensis was ruled by Berber kingdoms like the Kingdom of Altava. Only the coastal area around Saldae and Setifis remained fully Romanized. Byzantine emperor Maurice in 585 AD created the province of "Mauretania Prima" and erased the old Mauretania Sitifensis. Indeed, the emperor Maurice in that year 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 seat at Ravenna, and one in Africa, based at Carthage and including all imperial possessions in the Western Mediterranean. The first African exarch was the Patricius Gennadius: he was appointed as magister militum Africae in 578 AD, and quickly defeated the Romano-Moorish kingdom of Garmul in Mauretania extending the territory of the Mauretania Sitifensis. Among the provincial changes done by emperor Maurice, Mauretania Caesariensis and Mauretania Sitifensis were merged to form the new province of "Mauretania Prima". Mauretania Sitifensis initially had an area of 17800 square miles and had a good agriculture, that was exported through the port of Saldae. But under Byzantine control the province was reduced to only the coastal section, with one third of the original area.
