Al desmoronarse el Imperio Romano ante el empuje de los pueblos bárbaros, en el año 427 las Baleares caen en poder de los vándalos, que se apoderan rápidamente de la Bética (Andalucía) y del norte de África y establecen su capital en la antigua Cartago.
Los vándalos unen a su carácter cruel y sanguinario un fanatismo religioso: son fanáticos arrianos y pronto desatan contra los católicos una persecución tenaz. El rey Genserico manda a sus funcionarios requisar los objetos sagrados de las iglesias, incluso los lienzos litúrgicos para confeccionar prendas de vestir para sus soldados. Muerto Genserico en 477, le sucede en el trono y en la saña de perseguidor contra los católicos, Hunnerico. Basta leer el Martirologio Romano para encontrar grupos, a veces muy numerosos, de obispos, sacerdotes y fieles martirizados por este rey.
El obispo Macario de Menorca
El historiador Víctor Vitense trae una breve, pero interesante mención al obispo "Macárius de Minórica", que junto con los prelados de Mallorca y de Ibiza y otros muchos de los territorios dominados por los vándalos, en febrero del año 484 fueron obligados a ir a Cartago a dar razón de su fe ante el sanguinario perseguidor.
Nada más sabemos de este obispo, el segundo que conocemos de los antiguos pastores menorquines. Es casi seguro que fue el último prelado de los antiguos tiempos. Menorca iba a quedar largos siglos privada de obispo: hasta que se restableció la diócesis en 1795.
Fin del reino vandálico e incorporación al Imperio Bizantino.
En esta difícil situación, las voces suplicantes de los obispos y católicos perseguidos se dirigían hacia el emperador bizantino Justiniano. En junio de 533 una flota de quinientos navíos zarpó hacia el África y desembarcó entre Susa y Sfax un pequeño ejército de diez mil infantes y cinco mil jinetes, mandados por el más notable general bizantino de la época, Belisario. Aprovechando que las mejores tropas vándalas se hallaban reprimiendo una sublevación de Cerdeña, Belisario marchó contra Cartago, venció al rey Gelimer en Décimum (cerca de la actual Túnez) y se apoderó de la capital vandálica el 15 de septiembre; resistieron los vándalos por algún tiempo, hasta que, al cabo de tres meses Belisario aniquiló a los bárbaros e hizo prisionero a su rey.
El antiguo reino vandálico -y con él Menorca- pasó entonces a depender del lejano Imperio de Oriente. Volvió para la iglesia de la isla la libertad y la paz. Fueron restauradas las iglesias: la pila bautismal de la basílica de Son Bou parece ser de este período bizantino, así como los únicos restos de ajuar litúrgico encontrados: dos fragmentos de lampadario de hierro.
