Sezonul Serie B, 2003-2004 , marchează întoarcerea lui Messina în topul Italiei la 39 de ani de la ultima apariție a clubului Peloritan în Serie A, la 40 de ani de la ultima promovare. În ligă, Giallorossi au început prost, cu doar patru egaluri în primele șapte jocuri. După înfrângerea din derby-ul împotriva Catania , Pietro Franza decide să-l demită pe antrenorul Vincenzo Patania , înlocuindu-l cu Bortolo Mutti . Primul meci al lui Mutti pe bancă coincide cu prima victorie a echipei: 1-0 la Avellino . De acum înainte pentru Messina este o succesiune de rezultate excelente. [1] Așadar, primul tur se încheie cu Messina în zona de promovare completă, pe locul 4. În timpul pieței de transferuri din ianuarie, sosesc la Messina atacantulRoberto Sosa de la Ascoli și mijlocașulDomenico Giampà dalla Ternana , elemente care, în timpul turului doi, se vor dovedi a fi foarte prețioase. După ce a înscris doar un punct în primele trei meciuri de întoarcere, Messina obține o serie de rezultate excelente pentru care reușesc să fie promovate în Serie A cu o zi de rezervă. Victoria decisivă coincide cu ultima performanță a biancoscudati în meciurile oficiale de la Celeste[2] . În acea zi, luna iunie de 5, 2004 de , Messina bate acum retrogradat Como 3-0, cu o acoladă de la Arturo Di Napoli si un gol de la Alessandro Parisi , în timp ce în ultima zi au confirmat promovarea deja obținute, bate Torino pentru 3- 1 într-un Stadio delle Alpi semi-gol.
Messina închide campionatul pe locul 3, precedat de Palermo , Cagliari și la puncte egale cu Livorno . Di Napoli a fost golgheterul echipei, cu 19 goluri. Unele dintre cele mai prestigioase rezultate au fost victoriile acasă împotriva Fiorentinei cu 3-0 și împotriva Genovei cu 4-0.