De Byzantijnse periode
Noord-Afrika nam een belangrijke plaats in bij het plan van keizer Justinianus om het Romeinse Rijk te herenigen en de Germaanse koninkrijken te vernietigen. Zijn invasie van Afrika werd ondernomen tegen het advies van zijn deskundigen in (een eerdere poging in 468 was rampzalig mislukt), maar zijn generaal Belisarius slaagde, gedeeltelijk door de onbekwaamheid van de Vandalen. Hij landde in 533 met slechts 16.000 man, en binnen een jaar was het Vandalenrijk vernietigd. Er werd een nieuwe administratieve structuur ingevoerd, met aan het hoofd een praetoriaanse prefect met zes ondergeschikte gouverneurs voor burgerlijke zaken en een meester van de soldaten met vier ondergeschikte generaals.
Het duurde echter een twaalftal jaren om Afrika te pacificeren, deels vanwege stammenverzet in Mauretanië tegen de herinvoering van een geordende regering en deels omdat de ondersteuning van het leger in manschappen en geld gebrekkig was, wat leidde tot veelvuldige muiterijen. Onder Belisarius’ opvolger Salomo werd snel een opmerkelijk programma van fortificaties gebouwd, waarvan er vele bewaard zijn gebleven. Sommige waren garnizoensforten in het grensgebied, dat zich, althans een tijdlang, schijnt te hebben uitgestrekt ten zuiden van de Aurès en vervolgens noordwaarts van Tubunae tot Saldae. Maar ook veel overgebleven steden in het binnenland waren voorzien van aanzienlijke muren – bijvoorbeeld Thugga en Vaga (Béja, Tunesië). Na de dood van Justinianus (565) waren er nog meer moeilijkheden met de Mauretaanse stammen (de Mauri), maar de grootste schade werd aangericht door de nomadische Louata uit de Libische woestijn, die bij verschillende gelegenheden tot ver in Tunesië doordrongen.
Afrika toont een aantal voorbeelden van de massale hulp die Justinianus verleende bij het bouwen – en vooral versieren – van kerken en bij het herstellen van de christelijke orthodoxie, hoewel de overlevende Donatisten onvermijdelijk vervolgd werden. Hoewel ernstig verzwakt onder de Vandalen, behield de Afrikaanse kerk enkele sporen van haar kracht toen zij het verzet van de westerse kerken tegen het theologische beleid van de keizers in Constantinopel leidde – bijvoorbeeld dat van Justinianus zelf en ook dat van Heraclius en Constans II vlak voor de Arabische invasies.
Er is weinig bekend over de Byzantijnse periode in de Maghrib na de dood van Justinianus. De macht van het militaire element in de provincies nam toe, en aan het eind van de 6e eeuw werd een nieuwe functionaris ingevoerd, de exarch, wiens bevoegdheden bijna viceregaal waren. De economische omstandigheden gingen achteruit als gevolg van de toenemende onveiligheid en ook de beruchte corruptie en afpersing van het bestuur, hoewel het onmogelijk is te zeggen of dit in Afrika erger was dan in andere delen van het Byzantijnse Rijk. Het is zeker dat de bevolking van de steden slechts een klein deel was van wat zij in de 4e eeuw was geweest. Het hof van Constantinopel had de neiging Afrika te verwaarlozen vanwege de meer directe gevaren aan de oostelijke en Balkangrenzen. Slechts eenmaal in zijn laatste fase was het het toneel van een belangrijke historische gebeurtenis; in 610 zeilde Heraclius, zoon van de toenmalige Afrikaanse vorst, van Carthago naar Constantinopel in een opstand tegen de impopulaire keizer Phocas en volgde hem nog hetzelfde jaar op. Dat Afrika nog van enig belang was voor het keizerrijk bleek in 619; de Perzen hadden een groot deel van het oosten onder de voet gelopen, waaronder Egypte, en alleen Afrika bleek in staat geld en rekruten te leveren. Heraclius overwoog zelfs om Constantinopel te verlaten en naar Carthago te trekken, maar werd verhinderd door de gevoelens van het volk in de hoofdstad.
In het licht van het gebrek aan bewijsmateriaal voor de Byzantijnse periode, en de nog grotere onduidelijkheid rond de periode van de Arabische invallen en verovering (643-698) en de onmiddellijke nasleep daarvan, zijn conclusies over de toestand van de Maghrib aan het eind van de Byzantijnse overheersing speculatief. Een groot deel van het gebied was in handen van stammen, waarvan het niveau van de Romeinse cultuur in vele gevallen ongetwijfeld te verwaarlozen was. Zelfs voordat de Arabische aanvallen begonnen, lijkt het beeld er een te zijn van een voortdurend wegebben van de Latijnse beschaving en de Latijnse taal uit de hele Maghrib behalve langs de kustranden van Tunesië, en de ontwikkeling en uitbreiding van grotere stammengroepen, waarvan sommige, maar niet allemaal, christelijk waren. Ook het Byzantijnse bestuur was in zekere zin vreemd aan de Latijnse bevolking. De strijdkrachten die vanuit Constantinopel werden gezonden om de invasie tegen te houden, waren uiteindelijk ontoereikend, hoewel de Arabische verovering van de regio niet kon worden veiliggesteld voordat Carthago was veroverd en vernietigd en versterkingen over zee onmogelijk waren gemaakt. De meest vastberaden weerstand tegen de Arabieren kwam van nomadische Libische stammen die in het gebied rond het Aurès-gebergte leefden. De verwoestingen in de woongebieden tijdens de eerdere aanvallen, die niet veel meer waren dan grootschalige rooftochten, waren zeker immens. Er wordt wel beweerd dat het stadsleven en zelfs een geordend landbouwsysteem in die tijd bijna verdwenen zijn, hoewel sommige geleerden geloven dat een minimum hiervan overleefde tot de invasies van grotere nomadische groepen, met name de Banū Hilāl, in de 11e eeuw. Latijn werd nog gebruikt voor christelijke grafschriften in El-Ngila in Tripolitanië en zelfs in Kairouan (Al-Qayrawān) in de 10e en 11e eeuw. In de hele Maghrib echter arabiseerde de bekering van verschillende bevolkingsgroepen tot de Islam snel het grootste deel van de regio in taal en cultuur, hoewel de modaliteiten van deze ingrijpende veranderingen duister blijven.
De Belgische geleerde Henri Pirenne formuleerde een veelbesproken theorie dat de essentiële breuk tussen de oude en de middeleeuwse Europese werelden ontstond toen de eenheid van het Middellandse-Zeegebied niet door de Germanen maar door de Arabische invasies werd vernietigd. De geschiedenis van de Maghrib is een belangrijk element in dit debat, want daar kan men de volledige vervanging zien van een eeuwenoud politiek, sociaal, religieus en cultureel systeem door een ander binnen een kort tijdsbestek.