Il soprannome Pesce appare per la prima volta nel Chronicon di Francesco Pipino, un viaggiatore bolognese che, dopo aver narrato alcuni fatti riferendoli al 1239, parla di un giovane che fa vita da pesce da quando un giorno la madre, vedendolo sempre in mare, lo maledisse in preda alla stizza.
La maledizione materna é al centro dei versi che Fazio degli Uberti dedica al nuotatore:

Nicola bestemmiato dalla madre,
ch'ei non potesse mai dal mare uscire,
convenne abbandonar parenti e padre.
E poi volendo al precetto ubbidire
di Federico, nel profondo mare,
senza tornar mai su, si mise a gire'.

......

Nel sec. XVI la leggenda di Colapesce fa la sua apparizione in Spagna.
Pedro Mexia riferisce di aver sentito raccontare, durante la sua infanzia, di un Pesce-Cola simile al nuotatore di cui in seguito avrebbe letto la vicenda nell'opera degli scrittori italiani.
Per il Mexia Cola é un nuotatore catanese che, muovendosi senza prendere fiato, sale sulle navi che incontra dove i marinai lo accolgono dividendo con lui cibo e bevanda.
Durante una festa nel porto di Messina  il re di Napoli Alfonso getta in mare una coppa "di assai gran valore", promettendola in dono al nuotatore che "più tosto la ritrovasse".
Molti nuotatori "ragunati per far del lor nuotare prova" si lanciano in mare. Si lancia anche Colapesce che, finito in "qualche luogo concavo che in fondo era", non trova la via del ritorno.
Il Mexia così conclude: "Questa Istoria da duoi huomini di tanta autorità narrata, mi fa credere, che sia quel che favolosamente raccontano del pesce Cola le vecchie".
Gli scrittori ai quali il Mexia allude sono il Pontano e Alessandro D'Alessandro.

In tempi nei quali le nostre relazioni con la Spagna erano strette e frequenti, la leggenda di Cola Pesce se non importata o diffusa per la prima volta poté essere colà [... ] rinfrescata e rinverdita.
Così scrive il Pitré. Ne abbiamo una prova in un rarissimo libretto dei primi del sec. XVII, dove le avventure di Pece Nicolao sono localizzate nel piccolo borgo di Rota, a due leghe da Cadice, dove il pescatore medio hombre, y medio pescado era nato e dove, all'inizio del secolo, vivevano ancora i suoi discendenti.
L'abile nuotatore vive ancora nel mare, da dove di tanto in tanto viene fuori per informare i marinai delle sue scoperte e svelare loro segreti importanti sulla navigazione.

Nella seconda metà del Seicento la leggenda appare per la prima volta in Sicilia nelle opere di Tommaso Fazello e di Giulio degli Omodei.
Nella narrazione del Fazello Cola Pesce, catanese, vive coi pesci nel mare di Messina e sfida le tempeste per svelare agli uomini le meraviglie della natura. Durante una festa, il re (é Federico II) lancia tre volte in mare una tazza d'oro e costringe Cola a tuffarsi per riportarla alla luce. Cola pesca due volte la tazza e soccombe alla terza immersione.
Se alcuno - aggiunge il Fazello - volesse per qual cagione, o per qual virtù naturale questo Cola potesse vivere tanto sott'acqua, e senza respirazione, e riavere il fiato, ei debbe sapere che costui doveva avere i polmoni molto fungosi, e grandemente concavi: perocché gli animali ch'hanno i polmoni di così fatta sorte, non hanno bisogno di riavere spesso l'alito perché l'aria che gli hanno tirato una volta, si conserva lungo tempo ne'polmoni, e per questa cagione possono stare lungo tempo sott'acqua, come ne fa fede Aristotele nel libro della respirazione.

Il breve resoconto che della leggenda si legge in Maurolico nulla aggiunge al già noto.
Assai più ricco é invece il racconto dell'Omodei che, tra l'altro, riferisce di una persona religiosa e letteratissima, Oliviero Palmeri di Rosarno, che gli avrebbe confidato di aver parlato con molte persone che avevano conosciuto Cola di persona.
Erano queste le "cose meravigliose" che esse dicevano:
[ ... ] Cola, essendo figliuolo di una poveretta di bassa schiatta, fuggendo la fatica, come li putti più delle volte fanno, tutto il tempo consumava in andar nuotando nelle profondissime acque di maniera tale che, spinto quasi dall'abito e dalla fatica, che gliel'inclinava, divenne quasi dell'istessa natura dei pesci, e la maggior parte del tempo nel mare dimorava".
Nel mare intorno a Messina, dal Porto al Faro, non c'era luogo che Cola non avesse frugato. Nei giorni di festa i messinesi uscivano con le barche per vedere "lui e le sue meraviglie". Un giorno anche il re (qui é Ferrando) volle uscire con la sua galera per vederlo. Lo trovò su una spiaggia e lo accarezzò a lungo; poi lanciò in mare "una gioia ricchissima legata entro un anello" e ordinò a Cola di andare a raccoglierla.
Cola, "dimoratovi molto poco spazio", la riportò alla luce. Il re, stupito per l'abilità del nuotatore, lanciò la gemma ancora due volte. La terza volta andò a finire là dove c'era un polpo di smisurata grandezza, dal quale Cola aveva già rischiato una volta di essere ingoiato. I messinesi lo attesero invano.

Un riferimento alla leggenda di Colapesce si trova anche nel Don Quijte. Com'é noto, il Cervantes prese parte alla battaglia di Lepanto e proprio a Messina s'imbarcò sulla galera La Marquesa che lo portò nel luogo della battaglia. Ferito al petto e alla mano sinistra, di cui poi perse l'uso, trascorse a Messina un periodo di convalescenza.
Al cavallo andante, protagonista delle avventure narrate nel romanzo, non basta essere teologo, giurista, matematico, astronomo, medico, erborista: deve pure saper nuotare como dicen che nadaba el peje Nicolas o Nicolao.
 

Alla leggenda di Colapesce, una delle più conosciute, e da secoli e secoli [... ] raccontata per filo e per segno, il Pitré dedica ben 173 pagine della sua ricchissima silloge.

Dettagliata la descrizione che lo studioso ci dà della fortuna di cui essa ha goduto a partire dal sec. Xll. Letterati, scienziati, teologi, storici, filosofi si sono avvicinati al mitico nuotatore chi per dimostrare come si possa vivere lungamente sott'acqua, chi per descrivere una particolare conformazione dei nostri polmoni, chi istabilire un essere intermedio all'uomo e al pesce, chi per dare un'idea della natura del fondo sottomarino e delle comunicazioni che esso ha nello Stretto di Messina, o della ricchezza che il mare possiede e nasconde, chi per offrire un esempio della curiosità di un re capriccioso, o della debolezza di un povero palombaro.

Lo studio del Pitré é diviso in quattro parti:
- la leggenda scritta, dove sono indicati gli autori che, a partire dal sec. XI, hanno accolto nella loro opera echi della vicenda di Colapesce;
- la leggenda orale, dove le ragioni della vasta diffusione del racconto sono spiegate con "un fatto che solo la leggenda popolare ci offre: la conformazione subacquea di Messina, che ha del poetico e del pauroso;
- la leggenda nella letteratura, in cui il Pitré passa in rassegna gli autori che hanno preso il caso di Colapesce ad argomento di favole, di canti, di ballate, di romanzi, di drammi, di commedie e perfino di melodrammi;
- elementi, origine ed evoluzione della leggenda, dove lo studioso mette a fuoco gli elementi "storici" e "mitici" della leggenda, i suoi antecedenti e la consacrazione artistica che essa ha avuto ad opera di poeti e prosatori.

Infine il Colapesce di Dario Bellezza, un giovane che vive in una città di sole pulito e di mare cristallino. Un giorno il re, volendo soddisfare i capricci della "schizzinosa Principessina lo costringe ad immergersi per pescare una coppa e una collana. L'"anarchico" Cola si tuffa, ma non riemerge più:

Il tempo passava. Si fece sera;
una sera dai tersi colori.
La notte calò senza fretta.
La folla chiusa in un ermetico silenzio tornò alle proprie case.
Cola, l'anarchico, non riemerse.