戈达斯被派去负责并确保撒丁岛的忠诚。

他做了完全相反的事情，宣布撒丁岛独立于迦太基（Carthage），并与宣布代表希尔德里克宣战的尤斯提尼亚一世（Justinian I）展开谈判。

公元533年，格利默派遣其大部分军队和海军（120艘舰船和5000人）前往撒丁岛镇压戈达斯，结果惨重，汪达尔王国在贝利萨留斯（Belisarius）率领的尤斯提尼亚一世军队到达迦太基期间被彻底击溃。

汪达尔王国灭亡，撒丁岛回归罗马统治。

---

公元533年，当汪达尔人在贝利萨留（Belisarius）将军指挥下的尤斯提尼亚一世（Justinian I）军队在特里卡马鲁姆（Battle of Tricamarum）战役中被击败时，撒丁岛（Sardinia）重新回到了拜占庭帝国的统治之下。

贝利萨留斯将军派遣他的将军基里尔（Cyril）前往撒丁岛重新夺回这座岛屿。

撒丁岛在接下来的300年里一直处于拜占庭的统治之下，除了在公元551年被东哥特人（Ostrogoths）侵占的短暂时期。

在拜占庭统治下，岛屿被划分为称为“mereíai”的地区，由驻扎在卡拉利斯（Caralis）的法官治理，并由驻扎在福罗姆·特拉伊亚尼（Forum Traiani，现今的福尔东基亚努斯）的一支军队指挥。

此时，基督教在岛上的扎根更加深入，逐渐取代了在文化保守的内陆地区存活到早期中世纪的异教信仰。

除了世俗基督教，像凯撒利亚的巴西尔（Basil of Caesarea）这样的修道士的追随者也在撒丁岛上扎根。

虽然基督教传播到大部分人口中，但巴尔巴吉亚（Barbagia）地区仍然保持着大量的异教信仰，并且可能部分使用非拉丁语言。

他们重新建立了一个短暂独立的领域，拥有撒丁异教的世俗和宗教传统，其中一位国王是霍斯皮托（Hospito）。

教皇格雷戈里一世（Pope Gregory I）给霍斯皮托写了一封信，称他为“Dux Barbaricinorum”，并指出他作为基督徒是他人民的领袖和最优秀的人。

教皇在这封关于霍斯皮托的独特信中，敦促他让他的人民“如同无理智的动物一样生活，既不知道真神，又崇拜木头和石头”。

撒丁岛上的拜占庭统治结束的日期和情况尚不清楚。

至少在公元650年之前，拜占庭仍维持着直接的中央控制，此后，面对非洲总督格雷戈里（Gregory the Patrician）叛乱和穆斯林征服马格里布的第一次入侵，当地的代表获得了权力。

有证据表明，在公元697年阿拉伯人最终攻陷迦太基（Carthage）后，拜占庭在非洲的高级行政机构撤退到卡拉利斯。

失去对非洲的帝国控制导致阿拉伯人对撒丁岛的袭击逐渐增加，第一次袭击记录于公元703年，迫使该省增强军事自给自足。

在中央地中海地区，阿格拉比德王朝（Aghlabids）于公元870年征服了马耳他岛（Malta）。

他们还攻击或掠夺了撒丁岛和科西嘉岛（Corsica）。