Dopo aver conosciuto brevemente i Franchi nell’ultimo ventennio del terzo secolo, con il saccheggio di Siracusa, ed essersi salvata dai Visigoti di Alarico, che furono bloccati da una tempesta in Calabria, i Vandali, con a capo Genserico, nel 440, provenienti dall’Africa, sbarcarono a capo Lilibeo. Essi devastarono abbondantemente l’isola, infierendo, soprattutto, sui cristiani. Spinti dal vescovo ariano Massimino, uccisero  i vescovi Pascasino di Lilibeo e Massimiliano di Palermo. Quando, però, Genserico ebbe notizia di un esercito dell’impero d’occidente che stava marciando alla volta della Sicilia, nel 441, abbandonò frettolosamente l’isola. Nel 455, dopo il sacco di Roma, tornò a mettere a ferro e fuoco il territorio siciliano. Contemporaneamente anche un capitano ribelle dell’impero d’Oriente, Marcellino, arrivò in Sicilia, invadendola. Il patrizio svevo Ricimero mosse contro di lui sconfiggendo per primi i Vandali ad Agrigento, nel 456, e costringendo  poi Marcellino a fuggire in Dalmazia. Tuttavia Genserico non mollò la presa e ritornò. Stavolta dovette scontrarsi con l’esercito bizantino capitanato da Marcellino (che era stato perdonato da Leone, l’imperatore d’Oriente) e da Basilisco (fratello dell’imperatore stesso). Pur sconfitto, nel 463, riuscì ad incendiare la flotta nemica. La vittoria sostanziale gli permise di rimanere in Sicilia, fino a quando, nel 476, cadde l’Impero Romano d’Occidente. A quel punto, il vandalo cedette tutta la Sicilia a Odoacre, dietro compenso di un grosso tributo.
Nel 491, Il governo della Trinacria passò ai Goti. Nel 524 Giustino, imperatore d’Oriente, ordinò la chiusura di tutte le chiese ariane nei suoi territori. Per rappresaglia i Goti, anch’essi ariani, iniziarono a perseguitare i cristiani. Il governo di Teodorico, che fino a quel momento era stato sopportabile, divenne così pesante e duro per i siciliani che, alla sua morte, nacque la leggenda che fosse stato risucchiato all’inferno da un vulcano delle Isole Eolie.