536年复活节，因对所罗门的不满，一大群士兵发动了叛乱。所罗门与其秘书普罗柯比逃往被贝利撒留征服不久的西西里。所罗门派遣马丁努斯前往努米底亚的军队那里，并写信让狄奥多拉留下来负责迦太基的事务[6]。当听闻兵变后，贝利撒留带上所罗门以及100精兵，航向非洲。迦太基被9000名叛军包围，包括许多汪达尔人，皆由斯托察斯（英语：Stotzas）统领。贝利撒留出现之时，狄奥多拉在考虑投降。这位名将到来的消息使得叛军放弃包围并向西撤退。贝利撒留尽管只能召集到2000人，但是他立刻追击，在芒布尔萨附近赶上并击溃了叛军，但是大部分叛军逃脱，继续向努米底亚进军，当地的军队则加入了其中[7]。贝利撒留自己因平叛不得不返回意大利，查士丁尼则指派自己的侄子日耳曼努斯（英语：Germanus (cousin of Justinian I)）前往利比亚处理兵变。
在毛里塔尼亚，罗马人前哨塞普图姆（Septum）与凯撒毛里塔尼亚行省之间，自汪达尔人到来起，就有着诸多小的摩尔人王国，他们也统治着罗马化的城市人口。关于他们的信息很少，但是这些国家从未屈服于汪达尔人，而是声称为罗马帝国的延续，他们统治者也冠以诸如“英白拉多”（例如5世纪末期阿里斯（英语：Arris, Batna）首领马斯蒂埃斯（英语：Masties））、或“摩尔人与罗马人之王”（rex gentium Maurorum et Romanorum，例如6世纪早期阿尔及利亚东北部阿尔塔瓦（英语：Altava）之王马苏纳（英语：Masuna））的头衔[20]。
贝利撒留击败汪达尔人之后，罗马-摩尔人的国王们显然承认了罗马的宗主权（至少在名义上）。560年代末，摩尔人国王伽尔穆尔（英语：Garmul）（可能为马苏纳继任者）对罗马领土发动袭击，尽管未能夺得什么重要的城镇，但是根据比克拉洛的约翰（英语：John of Biclaro）的记载，连续三名将领（570年大区长狄奥多尔、陆军总长提奥克提斯图斯，571年提奥克提斯图斯的继任者阿马比利斯）都被伽尔穆尔的军队杀害[21]。其行动，特别是在与同时间西班尼亚西哥特人的袭击放在一起考虑时，对行省当局造成了显而易见的威胁。伽尔穆尔并非纯粹半游牧的部落的首领，而是一个拥有常备部队的成熟蛮族王国的领袖。新皇帝提比略二世重新委派托马斯为大区长，并让干将根纳迪乌斯（英语：Gennadius (6th century)）担任陆军总长，目标清晰地想要削弱伽尔穆尔的王国。准备工作漫长而严谨，但是这场发动于577年至578年的战争本身简短而有效率。579年，伽尔穆尔兵败被杀，廷吉塔纳与和凯撒两省之间的沿海走廊也得到了保全[22]。
根纳迪乌斯继续在非洲担任了很长时间的陆军总长，一直到590年代早期，他也成为第一位阿非利加总督（exarchus）[23][24]。皇帝莫里斯于580年代末建立阿非利加总督区时，将将民事权力与军事权力一并集中到根纳迪乌斯手中。总督区囊括了北非、西班牙的帝国领土、巴利阿里群岛、萨丁尼亚以及科西嘉。其相当繁荣，610年，非洲的军队推翻了福卡斯，希拉克略登上皇位。640年代起，总督区几乎成为了一个自治的实体，并一直存续到迦太基陷落（英语：Battle of Carthage (698)）于穆斯林人之手。
Cameron, Averil. Vandal and Byzantine North Africa. Late Antiquity: Empire and Successors A.D. 425-600, The Cambridge Ancient History Vol. XIV. Cambridge University Press. 2000: 552–569. ISBN 0-521-32591-9.
Cameron, Averil. Byzantine Africa: The Literary Evidence. University of Michigan Excavations at Carthage, Vol. VII. University of Michigan Press. 1982: 29–62.
Julien, C.A. (1931) Histoire de l'Afrique du Nord, vol. 1 - Des origines a la conquête arabe, 1961 edition, Paris: Payot
Martindale, John R.; Jones, A.H.M.; Morris, J. The Prosopography of the Later Roman Empire IIIa. Cambridge University Press. 1992. ISBN 0-521-20160-8.
Modéran, Yves. Les Maures et l'Afrique romaine, IV-VII siècle. 2003 （法语）.
Pringle, Denys. The Defence of Byzantine Africa from Justinian to the Arab Conquest: An Account of the Military History and Archaeology of the African Provinces in the Sixth and Seventh Century. Oxford: British Archaeological Reports. 1981. ISBN 0-86054-119-3.
.jpg)
