Già nel 1614 il rinvenimento delle reliquie sotto la Basilica da parte dell’Arcivescovo Manca de Çedrelles aveva suscitato enorme entusiasmo in tutta l’isola: nella relazione fatta al Re di Spagna Filippo III sul rinvenimento dei Corpi Santi si racconta che, in occasione del trasporto in processione delle reliquie a Sassari, il lungo percorso a piedi fu accompagnato da un concerto originatosi dal Cielo di tamburi, flauti, campane che suonavano a festa, la cui melodia riecheggiò soavemente in tutto il territorio circostante fino ai paesi della Gallura, generando una gioia indescrivibile in tutti coloro che ebbero la fortuna d’udirla.

Ancora a Manca de Çedrelles è legata la fama delle tre colonne con capitelli paleocristiani collocate nella parte occidentale della Basilica, tre su un lato del colonnato e una su quello opposto, a formare una sorta di croce, tanto che in antico le si attribuiva un particolare valore religioso; quando l’Arcivescovo nel Seicento cominciò lo scavo alla ricerca dei Corpi Santi iniziò proprio da questo punto, identificando subito tre sepolture anonime che attribuì erroneamente ai tre Martiri; solo con la prosecuzione dei lavori rinvenne la memoria paleocristiana e l’urna con le vere reliquie.

All’episodio del martirio è legata una leggenda che vuole che il punto in cui fu mozzata la testa ai martiri a Balai Lontano sia diventato “terra bruciata” e che in quel punto non cresca più erba; un’altra leggenda dice poi che non solo Gavino, ma tutti e tre i martiri furono gettati in mare dopo la decapitazione e i loro Corpi sarebbero riemersi da soli proprio nel punto in cui è stata costruita la chiesetta di Balai Vicino, nel luogo dell’antica prigionia;

inoltre fino agli Anni Quaranta del secolo appena trascorso si credeva che la chiesetta di Balai Lontano, il luogo di prigionia e di prima deposizione di Balai Vicino e il cosiddetto “Palazzo di Re Barbaro” fossero collegati tra loro da cunicoli sotterranei che sboccavano infine dietro una lapide murata nella cripta sotto la Basilica.

Alla Basilica e alla sua costruzione sono poi legate altre due leggende popolari.

La prima vuole che l’ultima colonna della navata settentrionale situata in direzione dell’abside occidentale, non lontana dall’attuale collocazione dell’organo, fosse stata “pescata in mare” dallo stesso San Gavino venuto in soccorso dell’architetto dell’edificio, al quale servivano ventidue colonne per realizzare il colonnato interno e al quale mancava appunto una colonna: per questo motivo i fedeli l’hanno baciata a lungo con venerazione, credendo che fosse perennemente trasudante, da cui la curiosa definizione di “colonna umida”.

Ancora nell’Ottocento i pellegrini che venivano a cavallo da tutto il Settentrione dell’isola in occasione della festa dei Martiri erano soliti entrare in mare a cavallo “in modo tale che l’animale fosse benedetto dalle acque dalle quali San Gavino tuffandosi aveva tratto l’ultima colonna mancante, uscendone poi a cavallo”.

Un’iscrizione su un elemento architettonico marmoreo di una parasta esterna della facciata settentrionale, presso la quale nel medioevo trovarono spazio ancora molte sepolture, menziona i nomi di due personaggi pisani, un Connullato e un certo Guido de Vada: la tradizione vuole che uno dei due nomi si riferisca all’Architetto costruttore dell’edificio, ma è stata smentita da recenti studi.

Infine fino al 1948 si credeva che i resti del giudice Comita fondatore della Basilica romanica fossero collocati entro l’urna di pietra collocata sopra il pilastro cruciforme di fronte all’ingresso principale: invece le sue spoglie furono sistemate entro lo stesso sarcofago nel quale furono deposte le ossa del Beato Gavino, dove appunto sono sistemati i resti di un “Comita rex”.

La fama dei Tre Martiri Gavino, Proto e Gianuario è stata tale nel corso dei secoli che il loro culto non solo si è radicato in diversi paesi dell’intera Sardegna, ma ha anche attraversato il mare raggiungendo la Corsica, la Campania e soprattutto la Toscana, dove in età medievale al Santo Gavino furono dedicati altri edifici di culto.