Nicola era nato e vissuto a Messina e figlio di un pescatore di Punta Faro. Cola era un ragazzo simile agli altri, solo che aveva moltissima passione per il mare: infatti stava giornate intere a contemplarlo. 
Egli aveva un infinito rispetto per i pesci e tutti quelli che il padre riusciva a prendere lui li ributtava in acqua in modo che vivessero. 
Sua madre era disperata, così un giorno, per rabbia, gli lanciò una maledizione:
- Possa diventare anche tu un pesce - così fu, gli spuntarono le pinne, le branchie, e le squame.

Nicola fu chiamato Colapesce e cominciò a vivere sempre più in mare e sempre meno in terra. Si gettava in mare dalla punta di Messina sprofondando giù e tirando, per divertimento, le code alle murene, cavalcava i delfini e quando, dopo alcuni giorni, tornava in superficie, raccontava tutte le meraviglie che aveva visto nelle profondità marine. Molti navigatori lo incontravano lungo le loro rotte e lui indicava il percorso più conveniente per evitare la rema e le burrasche. Colapesce era bravo corriere, infatti gli affidavano messaggi da portare in varie località; era capace di nuotare per oltre 100 chilometri e il capitano della città di Messina lo nominò palombaro.

Colapesce, che in realtà era un bel giovane, divenne così famoso che lo volle conoscere persino il re di Sicilia, il quale venne a Messina per sperimentare l'abilità di Colapesce. Fatto venire il giovane, il re con la sua nave, si portò nello stretto e lanciò in mare una coppa d'oro chiedendo a Colapesce di andare a prenderla. Quando egli risalì descrisse al re il paesaggio marino, i pesci e le piante che aveva visto. Il re, ancora più incuriosito, gettò la sua corona in mare in un punto più lontano: Cola si tuffò e cercò per due giorni e due notti; per due volte passò sotto la Sicilia fino a quando ritrovò la corona ed emerse dal mare. 
Il re gli chiese cosa avesse visto e lui rispose che aveva visto la Sicilia poggiare su tre colonne: una era rotta ma resistente, la seconda era solida come granito, la terza era corrosa e scricchiolante: gli disse anche che aveva visto un fuoco magico che non si spegneva.
Il re desiderava avere maggiori informazioni: buttò nell'acqua un anello e invitò Colapesce ad andarlo a ripescare e riferirgli cosa avesse visto. Il giovane era stanco e titubava ma il re insisteva e Colapesce non se la sentiva di dire di no. 
Decise di obbedire e disse che se si fosse visto risalire a galla l'anello di certo non sarebbe più risalito. Così si tuffò lasciando tutti in ansiosa attesa; dopo diversi giorni, quando il re stava decidendo di andar via, si vide galleggiare l'anello che bruciava. 
Il re capì che il fuoco esisteva veramente nel mare e si rese conto che Colapesce non sarebbe risalito mai più: era rimasto a sostenere la colonna corrosa.