Con la caduta dell’impero romano d’Occidente nel 476 Messina, città federata di Roma, subì un lento ed inesorabile declino.

La Sicilia fu conquistata dai Vandali e dai Goti e nel 535 dai Bizantini per opera del generale Belisario, i quali modificarono definitivamente il nome della città in Messina.

L’impero romano d’Oriente, però, era sempre più in difficoltà e gli Arabi  ne approfittarono per fare i primi tentativi per impadronirsi della Sicilia (740, 752-753 d.C.).

 La vera conquista iniziò nell’825, quando l’ammiraglio bizantino Eufemio da Messina si ribellò all’imperatore e si impadronì dell’isola. Ma Eufemio, in seguito ad alcune sconfitte contro l’esercito imperiale, fu costretto a rifugiarsi in Tunisia e chiese aiuto al sovrano aghlabita, esortandolo a impadronirsi dell’isola.

Nell’827 gli Arabi sbarcarono a Mazzara  e iniziarono la conquista della Sicilia. Messina, che aveva resistito strenuamente, fu presa  solo nell’ 843.

I nuovi conquistatori, dopo le atrocità della guerra, si dimostrarono alquanto clementi e, almeno virtualmente, alcune città, tra cui Messina, riuscirono a mantenere una certa indipendenza. Fu garantita la libertà di culto, anche se cristiani ed ebrei dovevano portare un indumento per farsi riconoscere e segnare le proprie case.

Palermo divenne la capitale e la politica economica dei musulmani determinò un importante sviluppo del commercio e dell’agricoltura.

Benchè l’isola nei due secoli di dominazione araba abbia goduto di un certo benessere, i siciliani, in realtà, non l’accettarono mai, bensì la subirono e  spesso scoppiarono violente insurrezioni.

A Messina  un gruppo di cittadini fondò la Compagnia dei Verdi, per difendere la fede cristiana dalle offese che, spesso, i saraceni non mancavano pesantemente di praticare, benché avessero garantito la libertà di culto.

La Compagnia dei Verdi, chiamata così per il colore delle insegne, è stata la più antica confraternita di Messina ed è ricordata per il coraggio e il sacrificio estremo con cui si batteva contro i musulmani infedeli.