Il luogo dove si trova la chiesa era legato al culto cristiano già nel VI secolo, come testimonia la vasca battesimale di epoca paleocristiana, oggi conservata sotto il presbiterio.

L'esistenza della diocesi di Dolia (attuale Dolianova) è attestata da fonti documentarie dal 1089 fino al 1503, anno in cui venne soppressa e inglobata nell'arcidiocesi di Cagliari. La cattedrale, dedicata a san Pantaleo, venne innalzata tra il XII e il XIII secolo.

La chiesa si presenta edificata in pietra arenaria, in stile romanico con alcune concessioni al gotico, risalenti all'ultima fase costruttiva (fine del XIII secolo). La facciata, i fianchi, l'abside a il campanile sono ornati da lesene e archetti pensili, lavorati con una grande varietà di decori scultorei, raffiguranti motivi geometrici, motivi antropomorfi e animali mitologici. Sul lato nord a fianco all'ingresso principale è presente una sorta di edicola o di protiro che probabilmente era anteposto ad un ingresso (attualmente murato). Questo elemento è costituito da due colonne che sorreggono un sarcofago di epoca romana sul quale a sua volta si elevano due colonnette che sorreggono una volta a sesto acuto.

L'interno è a tre navate, divise da pilastri cruciformi e polistili, i secondi in stile gotico; interessanti i capitelli scolpiti, dove sono rappresentate scene evangeliche, tra cui l'Adorazione dei magi e la Natività.