La Basilica di San Gavino Martire, costruita tra il 1030 e il 1080 in stile romanico pisano arcaico da architetti ed esecutori pisani, è probabilmente la più grande chiesa romanica in Sardegna. Fu costruita su un'antica basilica paleocristiana, sopra i luoghi dove si pensa furono sepolti i martiri Gavino, Proto e Gianuario, martirizzati in epoca tardo-imperiale. Quelle che si reputano le reliquie dei santi si trovano attualmente nella cripta, costruita nel Seicento sotto la navata centrale, alla quale si accede da una bella scalinata posta in una delle navate laterale, dove si trovano anche alcuni pregevoli sarcofagii romani in marmo.

Numerosi sono gli interventi di modifica che la Basilica subì nel corso della sua lunga storia: i primi lavori vennero eseguiti nell' XII secolo ad opera di maestranze lombarde, in seguito, alla fine del Quattrocento furono aperti nel lato meridionale i due portali gigliati in stile gotico-catalano, e solo sul lato sud un grande portale doppio, sempre nello stesso stile. La pianta è a tre navate divise da undici colonne in granito e in marmo, alcune delle quali prese direttamente dalla città romana, e da tre pilastri di calcare per parte, sui quali poggiano archi a sesto ribassato.