La stagione di Serie B, 2003-2004, segna il ritorno nel massimo campionato italiano del Messina a distanza di 39 anni dall'ultima apparizione del club peloritano in Serie A, a 40 anni di distanza dall'ultima promozione. In campionato i giallorossi partono male, con soltanto quattro pareggi nelle prime sette partite. Dopo la sconfitta nel derby contro il Catania, Pietro Franza decide di esonerare l'allenatore Vincenzo Patania, sostituendolo con Bortolo Mutti. Il primo match di Mutti in panchina coincide con la prima vittoria della squadra: 1-0 all'Avellino. Da questo momento per il Messina è un susseguirsi di ottimi risultati.[1] Così il girone di andata finisce con il Messina in piena zona promozione, al 4º posto. Durante il calcio-mercato di gennaio giungono a Messina l'attaccanteRoberto Sosa dall'Ascoli e il centrocampistaDomenico Giampà dalla Ternana, elementi che, durante il girone di ritorno, si riveleranno assai preziosi. Dopo aver conquistato un solo punto nelle prime tre partite di ritorno, il Messina ottiene una serie di ottimi risultati per cui riesce ad essere promossa in Serie A con una giornata d'anticipo. La vittoria decisiva arriva in coincidenza con l'ultima esibizione dei biancoscudati in gare ufficiali al Celeste[2]. In quel giorno, il 5 giugno 2004, il Messina batte l'ormai retrocesso Como per 3-0, con una doppietta di Arturo Di Napoli e un gol di Alessandro Parisi, mentre all'ultima giornata conferma la promozione già ottenuta, battendo il Torino (1-3) in uno Stadio delle Alpi semivuoto. Nella Coppa Italia il Messina gioca e vince solo la prima giornata, del gruppo 7, (2-0) contro il Pescara, non scendendo in campo nelle restanti due partite con Napoli e Salernitana, per protesta nei confronti dell'allargamento a 24 squadre del campionato cadetto, con quasi tutte le partecipanti al campionato di Serie B.
Con sei promozioni, il Messina chiude il campionato al 3º posto, preceduto da Palermo, Cagliari e a pari punti con il Livorno, salgono di categoria anche Atalanta e Fiorentina, quest'ultima giunta sesta, vince gli spareggi con la quart'ultima di Serie A, il Perugia. Arturo Di Napoli è stato il capocannoniere della squadra giallorossa, con 19 gol. Alcuni dei risultati più prestigiosi sono state le vittorie in casa contro la Fiorentina (3-0) e contro il Genoa (4-0), e a Torino (1-3).
calcio
Messina
Vincenzo Patania a seguire 
Triestina
Napoli
Vicenza
Cagliari
Piacenza
Salernitana.svg){kind=small}
Pescara
Verona
Fiorentina
Genoa
.svg){kind=small}
Ascoli
Torino