ヴァンダル戦争
この反乱は最終的には皇帝の従兄弟のゲルマヌス (en) によって鎮圧され、ソロモンは539年に復帰した。だが、彼は544年にムーア人とのキッリュウムの戦いで戦死してしまい、アフリカはまたも危機的状況に陥った。ムーア人とベルベル人の反乱に東ローマ軍は苦戦し、有能なヨハネス・トログリタ (en) 将軍によって548年に鎮圧されるまで続いた。
これ以降、アフリカは比較的安定して繁栄を享受することになり、584年に総督府 (en) が設置された。やがて、このアフリカ総督府からヘラクレイオス(在位:610年 - 641年)が現れ、暴君フォカス帝を打倒し、サーサーン朝やアヴァールを撃退して帝国を救う働きを果たすことになる。
だが、ヘラクレイオスはその晩年にイスラム勢力との戦いに敗れ、シリアとメソポタミア、エジプトを失った。その後も、東ローマ帝国はイスラム勢力の拡大を押し止めることができず、7世紀中頃にキレナイカとトリポリタニアを喪失する。カルタゴは697年にウマイヤ朝によって占領され、翌698年に完全に破壊されて歴史から姿を消した。
ヴァンダル王国を短期間で滅ぼしたユスティニアヌス帝は、翌535年にイタリアの東ゴート王国との戦争に踏み切った。この戦争でもベリサリウスが最高司令官を務め、一旦は東ゴート王ウィティギスを捕らえてイタリアを平定しかけたが、東ゴート族は新王を頂いて直ぐに再起し、戦争は20年近くに渡って続いた。最終的に帝国は553年に東ゴート族を滅ぼすことに成功したが、東ローマ帝国の国力は使い果たされ、後にイタリア半島の大部分をランゴバルド族に奪われることになる。
一方、アフリカでは534年4月に道管区長官職(praefectus praetorio)が設置され、東ローマ帝国の行政機関とともにかつてのローマの属州システムが再建された。続く数年間、アフリカ道管区長官と管区軍司令官(magister militum)を兼任するソロモンの元で、アフリカにおける東ローマ帝国の支配は強化されたが、内陸部のムーア人との戦闘は続いた。ソロモンは一定の勝利は収めたものの、536年に東ローマ軍のアリウス派兵士たちが大規模な反乱を起こし、彼の仕事は頓挫させられた。
ゲリメルはムーア人の助けを受けてヌミディアのパップア山に立て籠もった。ベリサリウスはヘルール族にこれを包囲させ、3ヶ月の包囲戦の末に飢えに苦しんだゲリメルは534年3月に東ローマ軍に降伏した。ゲリメルの降伏以前に東ローマ軍はサルデーニャ、コルシカそしてバレアレス諸島、マウレタニアとジブラルタル海峡の対岸にあるセプティムを制圧している。
この年の夏にベリサリウスはゲリメルとヴァンダル王国の財宝を伴ってアフリカを出立しており、この中にはエルサレム第二神殿の燭台(メノーラー)をはじめ、80年前のローマ略奪の際に持ち去られたものも多く含まれていた。ユスティニアヌス帝は過去のローマ帝国の栄光を意識し、古に倣いベリサリウスに凱旋式の挙行を許可した。皇帝以外の市民による凱旋式は紀元前19年のルキウス・コルネリウス・バルブス (en) 以来のことであり、同時にベリサリウスが最後となった。凱旋式の最中、満面の栄誉に浴している皇帝の姿を見たゲリメルはコヘレトの言葉を引いて「空の空。すべて空」と呟いたという。ゲリメルは皇帝から所領を与えられて引退し、捕虜となったヴァンダル兵は対ペルシャ戦線へ送られた。
ヴァンダル戦争は予想外の迅速かつ完全な勝利に終わり、帝国のかつての栄光を取り戻さんとするユスティニアヌス帝の信念を確固としたものにさせた。それを裏付けるように、新たに属州に加えられた行政組織に関する法律の前文にはこう書かれている。