La legendo de Colapesce estas legendo disvastigita en suda Italio, transdonita en multaj variaĵoj, kies originoj devenas de la 12-a jarcento, kiam la provenca poeto Raimon Jordan, kiu kantis "Nichola de Bar", kiu vivis kiel fiŝo.

Inter la 12-a kaj 13-a jarcentoj, la angla pastro Walter Map rilatas al "Nikolao", moknomita "Pipo", kiu vivis en la maro kaj sukcesis resti tie sen spirado. Li serĉis multekostajn aferojn en la fundo. Kiam reĝo Vilhelmo la 2-a volis renkonti lin, altirita el la maro, li mortis ĉe la brakoj de tiuj, kiuj volis porti lin al la reĝo.

Alia angla monaĥo en tiu tempo, Gervasio de Tilbury, raportas pri "Nikolao", moknomita "Papo", sperta maristo, naskita en Apulio, kiun la reĝo de Sicilio Roĝero la 2-a devigis malsupreniri en la maron el la lumturo por esplori la profundaĵojn. Sub la akvoj la naĝanto malkovris montojn, valojn, arbarojn, kampojn kaj kverkojn. "Nikolao" demandis la maristojn trapasantajn pri oleo por pli bone observi la marfundon.

Alia monaĥo, Salimbene de Adam el Parmo, rakontis en la dektria jarcento la legendon de la reĝo de Sicilio Frederiko la 2-a, kiu ordonis al Nikolao, naĝanto de Mesino, redoni al li oran tason, kiun li ĵetis pli profunde ĝis Nikolao malaperis en la abismo. En ĉi tiu versio unue aperas la rolulo de la patrino de Nikolao, kiu damnas sian filon.