بعد وفاة جستينيان في عام 565، تعرضت الإمبراطورية الرومانية الشرقية للهجمات من جميع الجهات بشكل متزايد، وغالبًا ما ترك الأباطرة المقاطعات البعيدة لتدبر أمرها بنفسها لفترات طويلة. ومع ذلك، استمر الضباط العسكريون، مثل هيرقلوس الأكبر (حاكم تقريباً من 598 إلى 610)، في التنقل بين المقاطعات الشرقية وإفريقيا. بحلول أربعينيات وخمسينيات القرن السابع، فقدت بيزنطة مقاطعة ميزوبوتاميا للمسلمين، الذين قضوا أيضًا على منافس البيزنطيين، الإمبراطورية الساسانية (651). ونتيجة لذلك، فقدت القسطنطينية مصدرًا مهمًا للضباط ذوي الخبرة الذين تم تأهيلهم من خلال الحروب المستمرة على الحدود مع الفرس. استمرت سلالة هيرقليوس (610-711) في تعيين بعض الضباط الشرقيين الكفوئين في المناصب الإفريقية، مثل الأرمني نارسيس، الذي قاد طرابلس، ويوحنا، دوق تيغيسيس. يُخمّن والتر كاجي أن بعض الضباط الأرمن قد يكونون طلبوا الانتقال إلى الشرق للدفاع عن أوطانهم مع تقدم المسلمين إلى أرمينيا، ولكن المصادر صامتة بشأن ذلك. ومع ذلك، فإن الضباط الذين استمروا في الوصول من الشرق بعد فقدان ميزوبوتاميا كانوا أكثر تأقلمًا مع الهزائم مثل معركة اليرموك (636) من الاستراتيجيات الناجحة السابقة ضد الساسانيين، وكانت الاستراتيجيات والتكتيكات الجديدة تتطور ببطء
النظام الإداري الروماني المتأخر
أنشأ ديوكلتيانوس نظامًا إداريًا رومانياً تميز بوضوح بين المناصب المدنية والعسكرية، وذلك لتقليل احتمال التمرد من قبل الحكام الإقليميين ذوي السلطة الكبيرة. تحت حكم جستينيان الأول، تم عكس هذه العملية جزئيًا في المقاطعات التي كانت تعتبر عرضة للخطر أو في حالة فوضى داخلية. بناءً على هذا السلوك واستمراراً له، أنشأ الإمبراطور موريس بين عامي 585 و590 منصب الإكسارخ، الذي جمع بين السلطة المدنية العليا لمثيل البريتور و السلطة العسكرية لماجستير ميلتيوم، وتمتع بقدر كبير من الاستقلال عن القسطنطينية. تم تأسيس إكسارخيتين، واحدة في إيطاليا، ومقرها في رافينا (وتعرف باسم إكسارخية رافينا)، والأخرى في إفريقيا، ومقرها في قرطاج وتضم جميع الممتلكات الإمبراطورية في البحر الأبيض المتوسط الغربي. كان أول إكسارخ إفريقي هو الباتريشيوس جيناديوس.
فيما يتعلق بالتغييرات الإقليمية، تم فصل طرابلس عن مقاطعة إفريقيا ووضعها تحت ولاية مصر. كما تم دمج موريطنية قيصرينسيس وماوريتانيا سيتيفينسيس لتشكيل مقاطعة جديدة تحت اسم "موريطنية برايما"، بينما تم دمج ماوريتانيا تنجيتانا، التي اقتصرت فعلياً على مدينة سبتة (سبتة الحالية)، مع الحصون الساحلية الإسبانية وجزر البليار لتشكيل "ماوريتانيا سيكندا".
كانت المملكة القوطية الغربيّة تهديداً مستمراً للإكسارخية. كان الإكسارخ الإفريقي يسيطر على ماوريتانيا الثانية، التي كانت مجرد موقع صغير في جنوب إسبانيا. استمر الصراع حتى الاستيلاء النهائي على آخر معاقل إسبانيا حوالي عام 624 من قبل القوط الغربيين. احتفظ البيزنطيون فقط بحصن سبتة (سبتة الحديثة)، عبر مضيق جبل طارق.
خلال الثورة الناجحة للإكسارخ في قرطاج، هيرقلوس الأكبر وابنه الذي يحمل نفس الاسم هيرقلوس في عام 608، كان البربر يشكلون جزءًا كبيرًا من الأسطول الذي نقل هيرقلوس إلى القسطنطينية. بسبب الطموحات الدينية والسياسية، أعلن الإكسارخ غريغوريوس الباتريشيوس (الذي كان مرتبطًا بالأسرة الإمبراطورية عبر ابن عم الإمبراطور نيكيتاس) استقلاله عن القسطنطينية في عام 647. في ذلك الوقت، تجلى تأثير وقوة الإكسارخية في القوات التي جمعها غريغوريوس في معركة سفيتولا في نفس العام، حيث قاتل أكثر من 100,000 رجل من أصل أمازيغي لصالح غريغوريوس.
الفتح الإسلامي
في عام 647، بدأت أولى الحملات الإسلامية بمبادرة من مصر تحت قيادة الأمير عمرو بن العاص وابن أخيه عقبة بن نافع. مستشعرين ضعف الرومان، غزا المسلمون برقة في ليبيا ثم انتقلوا إلى طرابلس حيث واجهوا مقاومة.
بسبب الاضطرابات الناتجة عن الخلافات اللاهوتية حول المونوثيليتيزم والمونوإينرجيزم، ابتعدت الإكسارخية تحت حكم غريغوريوس الباتريشيوس عن الإمبراطورية وأعلنت تمردها. زادت تدفقات اللاجئين من مصر (خاصة الملقطية)، وفلسطين، وسوريا من التوترات الدينية في قرطاج ورفعت مستوى التنبيه لدى غريغوريوس بشأن التهديد العربي الوشيك.
مستشعراً أن الخطر الأكثر إلحاحاً جاء من القوات المسلمة، جمع غريغوريوس حلفاءه وواجه المسلمين، لكنه هُزم في معركة سفيتولا، العاصمة الجديدة للإكسارخية، حيث انتقل غريغوريوس إلى الداخل لتحسين الدفاع ضد الهجمات الرومانية من البحر.
بعد ذلك، أصبحت الإكسارخية دولة شبه تابعة تحت حكم إكسارخ جديد يدعى جيناديوس. محاولة الحفاظ على وضع التبعية للقسطنطينية ودمشق ضغطت على موارد الإكسارخية وأثارت اضطرابات بين السكان.
حققت الإكسارخية انتصاراً كبيراً على قوات عقبة بن نافع في معركة فسكيرا عام 682، بمساعدة الملك الأمازيغي كُسَيْلا. أجبرت هذه الهزيمة القوات المسلمة على التراجع إلى مصر، مما منح الإكسارخية فترة هدنة دامت عقداً من الزمن. ومع ذلك، أدت المواجهات المتكررة إلى استنزاف موارد الإكسارخية المتضائلة والمقسمة بشكل متزايد.
في عام 698، سحق القائد المسلم حسن بن النعمان وقوة من 40,000 رجل قرطاج. كان العديد من المدافعين عنها من القوط الغربيين الذين أرسلهم ويتيزا للدفاع عن الإكسارخية، حيث كان ويتيزا أيضاً يخشى التوسع المسلم. قاتل العديد من القوط حتى الموت؛ وفي المعركة التالية، تحولت قرطاج مرة أخرى إلى أنقاض، كما كانت قبل قرون على يد الرومان.
كان فقدان الإكسارخية الإفريقية في البر الرئيسي ضربة هائلة للإمبراطورية البيزنطية في غرب البحر الأبيض المتوسط، حيث كانت قرطاج ومصر المصدرين الرئيسيين للعمالة والحبوب للقسطنطينية. لم يستعد البيزنطيون أراضيهم في إفريقيا أبدًا.
كما ذُكِرَ في كتاب الرتب والوظائف. قام دقلديانوس، حوالي 293 بإعادة هيكلة إدارة المقاطعات وإنشاء الأبرشيات. بعد وفاة قسطنطين الأول أُنشِئَت ولايات إمبراطورية دائمة. انقسمت الإمبراطورية بشكل دائم بعد 395. أُسِّسَت الإكسارخيات (Exarchates) في رافينا وأفريقيا بعد 584. بعد خسارة كبيرة للأراضي في القرن السابع، حل نظام الثيمة محل المقاطعات حوالي 640-660، وفي آسيا الصغرى وأجزاء من اليونان ظل نظام الثيمة سائدا حتى أوائل القرن التاسع.