أسس الإمبراطور البيزنطي موريكيوس عام 585 م مقاطعة «موريتانيا بريما» وسحق «موريطنيا سيتيفينسيس» القديمة. أنشأ الإمبراطور موريكيوس في ذلك العام منصب ضابط «إكسرخس» الذي يجمع السلطة المدنية العليا (قائد برايتوري) والسلطة العسكرية (قائد الجنود) ويتمتع بحكم ذاتي كبير عن القسطنطينية، أُنشئ إكسرخسيتين الأولى في إيطاليا مركزها رافينا (تعرف بـإكسرخسية رافينا) والثانية في أفريقيا مركزها قرطاج وتشمل جميع الممتلكات الإمبراطورية في غرب البحر الأبيض المتوسط، كان جيناديوس أول إكسرخس لإفريقيا، عُيّن قائدًا لجنودأفريقيا عام 578 م فسرعان ما هزم مملكة غارمول الرومانية المورية في موريطنية ومدد أراضي «موريطنيا سيتيفينسيس». من بين التغييرات الإقليمية التي قام بها الإمبراطور موريكيوس، دُمجت كل من موريطانيا القيصرية وموريطنيا سيتيفينسيس لتشكيل المقاطعة الجديدة «موريتانيا بريما».
في البداية كانت مساحة موريطنيا سيتيفينسيس تبلغ 17,800 ميل مربع (46,000 كيلومتر مربع) وكانت لديها منتوجات زراعية جيدة (الحبوب، القمح، الشعير، الزيتون... إلخ)، تُصدر عبر ميناء صالداي.[6][7] تقلصت المقاطعة تحت السيطرة البيزنطية إلى القسم الساحلي فقط إلى ثلث المساحة الأصلية فقط.