Gli scavi archeologici effettuati da Palermo a Siracusa hanno riportato alla luce interi cimiteri, situati intorno alle città e utilizzati a partire dalla fine dell'antichità, quando la Sicilia viene cristianizzata dai Romani. Le catacombe, principalmente quelle ritrovate a Siracusa (IV-V sec.) che conservano alcune tracce di decorazioni pittoriche, sono quindi le prime testimonianze d'arte cristiana. Come in tutto il mondo paleocristiano, la Sicilia può assistere poco per volta all'edificazione di chiese, ispirate all'antico modello basilicale di origine latina: un semplice rettangolo, diviso in tre navate da colonne e prolungato ad est da un'abside centrale, come quello della chiesa di San Giovanni Evangelista a Siracusa (purtroppo diruta). Più imponenti appaiono le chiese allestite in templi antichi, tra cui il tempio della Concordia ad Agrigento e quello di Atena a Siracusa: nelle pareti della cella vengono aperte arcate, mentre vengono colmati gli spazi che si aprivano tra le colonne situate intorno al tempio.
Nel 535, la conquista dell'isola da parte dei Bizantini segna il riavvicinamento della Chiesa di Sicilia all'esarcato di Ravenna e, a partire dal 751, all'impero di Costantinopoli. E' tuttavia la crisi iconoclasta che colpisce Bisanzio a dare la svolta decisiva alla storia della regione. I cristiani di Sicilia infatti, rimasti fedeli al culto delle figure sacre vietate dall'imperatore nel 725, assistono all'arrivo in massa di immigrati. Intere comunità monastiche e numerosi gruppi di artisti si rifugiano in Sicilia dove fanno mostra delle loro doti, specialmente nel campo dei mosaici.
Questo florido periodo dà origine da un lato all'allestimento di numerosi santuari (tra cui quelli di Cava d'Ispica e Pantalica) e alla costruzione di abitazioni rupestri scavate direttamente nella roccia (quasi tutte scomparse), dall'altro all'edificazione delle cube, chiesette a pianta centrata quadrata (tipicamente bizantine) semplicemente formate da tre esedre che si affacciano su un'area centrale cubica, sormontata da una cupola, con un ingresso situato nell'unico lato piatto (ad ovest). Ne sussistono alcuni esempi nella parte orientale dell'isola, a nord e ad est dell'Etna (Castiglione di Sicilia, Randazzo, Rometta, Santa Venerina), nei pressi di Noto (Citadella) e nei dintorni di Siracusa. Gli altri monumenti probabilmente eretti durante il periodo bizantino, vengono completamente modificati, smembrati o adibiti ad altro uso e non sopravvivono alle civiltà successive. E' certo che sono i Bizantini ad importare l'arte musiva sull'isola, ma è possibile conoscere la loro abilità in questo campo solamente attraverso le opere realizzate durante il regno dei Normanni.