Roma İmparatorluğu'nun İmparator Diocletianus'un daha sonraki bölünmesinde, Saldae'den Ampsaga nehrine kadar olan Mauretania Caesariensis'in doğu kısmından yeni bir eyalete oluşturuldu ve yeni eyalet, denizden uzak Setifis (modern Cezayir'de Setif) kasabasına atfen Mauretania Sitifensis (modern Cezayir'de Setif) olarak adlandırıldı.[2]
Mauretania Sitifensis'in belirli alanlarda Vandal ve Bizans yönetimindeyken, çoğunluğu (578 AD yılına kadar) Altava Krallığı gibi Berberi krallıkları tarafından yönetiliyordu. Sadece Saldae ve Setifis çevresindeki kıyı bölgesi tamamen Roma kültürünü taşıyordu. 585 AD yılında Bizans İmparatoru Mauricius, "Mauretania Prima" eyaletini kurdu ve eski Mauretania Sitifensis'i sildi. Doğrusu imparator Mauricius aynı yıl "Eksarh" makamı kurmuştu, bu makam Praefectus praetorio yüksek sivil yöneticisi ile magister militum askeri yöneticisinin bir araya gelmesiydi ve Konstantinopolis'ten hatırı sayılır özerkti.
Biri İtalya'da Ravenna'da (dolayısıyla Ravenna Eksarhlığı olarak bilinir) ve diğeri Afrika'da Kartaca merkezli ve Batı Akdeniz'deki tüm imparatorluk mülklerini de içeren iki eksarhlık kuruldu. İlk Afrika eksarhı Patrici Gennadius idi: 578'de Magister militumAfricae olarak atandı ve Mauretania Sitifensis'in topraklarını genişleterek Mauretanya'daki Romano-Moro Garmul Krallığı'nı hızla yendi. İmparator Mauricius tarafından yapılan eyalet değişiklikleri arasında Mauretania Caesariensis ile Mauretania Sitifensis eyaletlerinin birleştirilip yeni "Mauretania Prima" eyaletinin oluşturması vardı.
Mauretania Sitifensis başlangıçta 17.800 mil karelik bir alana sahipti ve Saldae limanından ihraç edilen iyi bir tarımı (tahıllar vb.) vardı.[4] Ancak Bizans kontrolü altında eyalet, orijinal alanın üçte biri ile sadece kıyı kesimine indirildi.
Arrowsmith, Aaron. A Compendium of Ancient and Modern Geography. Editor E.P. Williams, 1856 (New York Library) New York, 2007
Serge Lancel et Omar Daoud. L'Algérie antique : De Massinissa à saint Augustin, Place des Victoires, 2008 (9782844591913)
Martindale, John R., (Ed.) (1992). The Prosopography of the Later Roman Empire: Volume III, AD 527–641 (İngilizce). Cambridge: Cambridge University Press. ISBN0-521-20160-8.
Shlosser, Franziska E. (1994). The Reign of the Emperor Maurikios (582–602). A reassessment (Historical Monographs 14) (İngilizce). Atina.