È una delle più note leggende della città. Narra delle gesta di un valente pescatore capace di vivere sia in terra sia in acqua.

La prima versione narra che Cola, avendo raggiunto gran notorietà, fu invitato a partecipare alle prove, superate le quali avrebbe avuto in sposa la figlia di Federico.
Questa, ragazza molto bella ma capricciosa, gettò nelle acque dello Stretto uno dei suoi anelli d'oro sfidando Cola a riprenderlo e a riportarglielo. Cola si tuffò in mare; dopo breve tempo riemerse con l'anello. Superata questa prima prova, la principessa ripete il gesto una seconda ed una terza volta, sino a quando, aumentate profondità e difficoltà, il valente pescatore non riemerse più.

La seconda versione prevede che sia stato lo stesso Federico a sottoporre a prove successive il bravo Cola. Prima gettando in mare una coppa d'oro e chiedendogli di recuperarla, poi chiedendogli quali fossero le condizioni dei fondali su cui poggiava la Sicilia. Il buon Cola, ritornato dalla ricognizione riferì all'imperatore che una colata di fuoco stava avvenendo nelle acque tra Messina e Catania. L'imperatore, incredulo, chiese al pescatore di portargli la prova di quanto aveva asserito. Come avrebbe potuto il bravo Cola prendere il fuoco con le mani? In ogni modo, per non dispiacere il proprio sovrano, s'immerse nuovamente e nel tentativo di portare a termine l'impossibile impresa, trovò la morte.

La terza versione consiste nel tentativo di recupero di una palla da cannone sparata dalla spiaggia di Faro. Cola, dopo aver inseguito la palla di cannone che affondava velocemente, la recuperò. Quando stava per risalire si ritrovò, prodigiosamente, in una bolla d'aria entro cui rimase imprigionato, non potendo nuotare per risalire in superficie. (versione tratta da "Storie e leggende napoletane" di Benedetto Croce).

La quarta versione, narra che Cola immersosi nei profondi abissi dello Stretto si accorse che una delle tre colonne che reggevano la Sicilia fosse lesionata e si stava sempre più sgretolando, minacciando di far sprofondare la sua amata Messina. Per evitare ciò, si sostituì alla colonna pericolante ed ancora oggi è possibile trovarlo a compiere questa funzione. In questa versione è possibile cogliere riferimenti alla sismicità del nostro territorio, già nota in tempi medioevali e trasposta nel linguaggio e nella tradizione popolare.

La leggenda di Cola Pesce è nota anche in altre parti d'Italia (Palermo e Napoli) ed perfino in Spagna.