La leggenda di Cola Pesce (chiamato anche Pescecola o Nicola pesce o semplicemente Cola) ha avuto una notevole fortuna nella letteratura popolare, ed è quindi abbastanza famosa in tutta l’Europa mediterranea ed occidentale.
Essa si rifà a due filoni, quello scritto e quello orale, che, pur se basati sulle medesime sequenze, mostrano, com’è logico, delle differenze negli episodi secondari.
La tradizione scritta risale almeno al XII secolo, al trovatore Raimon Jordan, ma si stabilizza nella sua stesura più complessa tra XV e XVI secolo.
È curioso il fatto che, sebbene la storia sia concordemente ambientata nell’Italia meridionale, e precisamente in Puglia secondo i primissimi autori ed in Sicilia secondo la quasi totalità degli altri, fino al XVI secolo avanzato nessuno scrittore di queste regioni vi abbia fatto il minimo cenno. Anzi, le fonti più antiche sono tutte straniere (francese Jordan, inglesi Walter Mapes e Gervasio di Tilbury), e quelle successive del nord-Italia (parmense Fra’ Salimbene, bolognese Francesco Pipino, ferrarese Ricobaldo).
Nella sua versione colta, risultante da queste versioni scritte, la leggenda si può cosi sintetizzare.
Cola o Nicola era un ragazzo siciliano (pugliese solo per 4 autori su 25) che si dilettava continuamente a sguazzare nel mare, e capace di resistere un tempo inusitato sotto l’acqua.
La sua figura, non sempre descritta, sembra essere anfibia, anche se non di vero e proprio uomo-pesce, perché a volte sono citati piedi e mani palmate.
Un re (in genere Federico II) lo vuole mettere alla prova, e lo incita ad immergersi nei gorghi per descrivere il mondo sottomarino. La tentazione di un gioiello in premio, (per lo più un anello) gettato in mare, vince le resistenze di Cola, che si immerge, e torna, raccontando le meraviglie viste. Il re lo tenta di nuovo, gettando altri ori, ma questa volta Cola non torna più.
Nella tradizione orale le principali varianti riguardano la forma di Cola, i motivi di questa, e la descrizione del mondo sottomarino.
Secondo i racconti Cola era un ragazzo normale, ma tanto innamorato del mare da passarvi tutto il suo tempo; un giorno la madre, esasperata dal suo atteggiamento, lo maledì dicendo:
- Che tu possa diventare un pesce!
Da allora Cola assunse l’aspetto di un uomo pesce, con tanto di coda e squame.
Quando, spinto dal re, Cola discende negli abissi, vede con terrore che la Sicilia è retta da tre colonne, una delle quali e già rotta, e la seconda incrinata. Il re insiste per saperne di più, ed alla seconda o alla terza discesa, il povero Cola muore.

È curioso che sotto il medesimo nome di Nicola, siano state raccolte leggende di pesci straordinari semi-umani, in una vasta area che va dalla Spagna alla Bretagna, alla Grecia, e perfino al Sudan.
La corrispondenza del nome, più che ad una trasposizione della leggenda, di cui peraltro mancano i contenuti, si deve probabilmente alla identificazione di Nicola con S. Nicola di Bari, patrono dei marinai, e da qualcuno definito come il successore cristiana del dio Nettuno.