Le loro reliquie sono custodite nella cripta secentesca, grande quanto la navata centrale e realizzata dopo il poderoso scavo condotto nel 1614 dall’Arcivescovo di Sassari, Gavino Manca de Cedrelles, per ricercare il luogo di sepoltura dei tre santi, del quale al tempo si era persa memoria. Ritrovate le reliquie, si decise di edificare la lunga galleria-santuario per custodirle in modo conveniente.
Nella cripta-antiquarium sono presenti cinque splendidi sarcofagi dei secoli III-IV appartenenti alla necropoli di Turris Libisonis, un sarcofago medievale, i resti di una cappella funeraria del IV secolo, cinque statue settecentesche in marmo di Carrara, tre delle quali, realizzate dallo scultore genovese Giacomo Antonio Ponzanelli, raffigurano i tre Martiri Turritani, e altre dodici realizzate in terracotta smaltata nel XIX secolo.
Nell'anticripta, articolata su tre lati da nicchie in forme rinascimentali, furono sistemate cinque pregevoli statue marmoree seicentesche dei Santi Gavino, Proto, Gianuario, Gabino e Antioco. In seguito ne furono aggiunte delle altre in stucco. L'area fu delimitata da robuste cancellate costruite in difesa dalle profanazioni degli infedeli, tanto che il re di Spagna Filippo III ordinò che la chiesa fosse trasformata in fortilizio. Nella cripta troviamo un'antica chiesa risalente al VII-VIII secolo e le reliquie dei Martiri Turritani Gavino, Proto e Gianuario prelevate dopo il 1000 dalla loro tomba di Balai, rinvenute in seguito agli scavi effettuati nel 1614 in corrispondenza dell'intera navata centrale e commissionati dall'arcivescovo Gavino Manca de Cedrelles.
Il suo interno è costituito da tre navate, coperta a capriate la centrale e a volte a crociera le laterali, da sei pilastri, da ventiquattro colonne con capitelli romani e paleocristiani e da un monumentale portale in stile gotico-aragonese; i suoi lunghi fianchi si sviluppano in due absidi contrapposte, rendendola una fra le più belle chiese romaniche italiane e la più grande della Sardegna.
Dell'arredo settecentesco restano una statua equestre lignea di San Gavino e i venerati simulacri dei Corpi Santi dei Martiri. Questi ultimi vengono trasportati in processione e fatti sostare dal 3 maggio fino alla Pentecoste nella chiesetta di San Gavino a Mare, nella vicina regione di Balai; questa cappella, insieme all'ancor più piccola chiesetta di Balai Lontano, costituisce un'appendice della Basilica.
Nel piazzale antistante la Chiesa di San Gavino troviamo la colonna di cipollino su un basamento settecentesco, che reca sul capitello la statuetta equestre del Santo. Gli altri spazi attorno alla Basilica sono denominati Largo Sabelli, Piazzale Santi Martiri Turritani, Atrio Metropoli Turritana e Atrio Giudice Comita.
