La basilica è situata tra due cortili, detti "atrio Comita" e "atrio Metropoli", su cui si affacciano i due lati lunghi dell'edificio. Nel fianco meridionale si apre l'ingresso principale, costituito da un pregevole portale gemino del XV secolo in stile gotico-catalano; il grande arco a tutto sesto che sovrasta il portale è retto da colonnine e presenta la cornice dell'estradosso che poggia su due capitelli scolpiti con la raffigurazione di due angeli che reggono uno stemma ciascuno. La chiesa è biabsidata con absidi contrapposte infatti ce n'è una su entrambe i lati corti della basilica. Il paramento esterno della fabbrica, in pietra calcarea, è scandito da lesene e archetti pensili. La copertura del tetto è in lastre di piombo.
L'interno è a pianta rettangolare, diviso in tre navate tramite due serie di archi a tutto sesto retti da ventidue colonne di spoglio, in granito rosa e marmo grigio, e da tre coppie di pilastri cruciformi. I capitelli sono quasi tutti di epoca romana. La pianta a sviluppo longitudinale è conclusa su ambo i lati minori da un'abside. La navata centrale, molto più larga di quelle laterali con un rapporto di 3:1, è coperta a capriate lignee che riportano diverse scritte in colore rosso risalenti al XVII secolo, mentre le campate delle navatelle laterali sono voltate a crociera. Attuali studi effettuati dall'Università di Pisa stanno rilevando l'intero corpo basilicale con i più recenti metodi di scansione laser e fotogrammetria.
L'altare maggiore, fino alla metà del XX secolo collocato al centro della navata entro una quinta in stile gotico catalano, si trova ora nell'abside situata a sud ovest, ridotto a semplice mensa (è stato demolito anche il pregiato coro e altri altari secondari) mentre l'abside contrapposta, a nord est, ospita un catafalco ligneo del XVII secolo con le statue policrome dei santi martiri Gavino, Proto e Gianuario, raffigurati in posizione giacente.
Dalle navate laterali si accede all'anticripta e alla cripta, dove sono custoditi artistici sarcofagi romani, dentro i quali si conservano le reliquie dei martiri turritani. L'anticripta è un ambiente in stile classico rinascimentale, caratterizzato da numerose nicchie entro le quali si collocano statue marmoree di martiri locali.