Una delle più note in Puglia, è il risultato di una serie di modifiche progettuali e di successivi rimaneggiamenti (XII-XIII secolo), come pure della sapiente fusione di elementi nordici di gusto gotico sul ceppo romanico. Spioventi assai inclinati racchiudono la facciata, nella quale si aprono in basso tre portali. È quello centrale il più lavorato: da leoni partono esili colonnine terminanti in grifi alati, sui quali si impostano archi, con simboli degli evangelisti e i 12 apostoli, volti alla centrale figura di Cristo. In alto è una bifora con soprastante rosone; la serie di archetti pensili al di sotto degli spioventi prosegue nei fianchi, impreziosita da teste umane e animali o da motivi vegetali. Sulla destra della chiesa, staccato e arretrato, si erge il campanile.<br>Dopo l'eliminazione del soffitto settecentesco, l'interno, a tre navate su pilastri e altrettante absidi, ha riacquistato le linee originarie: sopra le navi corre un ballatoio su mensole figurate che funge da sostegno alle bifore e alle trifore del finto matroneo; il frammento di affresco con la Vergine in trono e il martirio di S. Sebastiano è cinquecentesco. Sotto la Cattedrale, un percorso ipogeo evidenzia resti romani, dell'antico edificio e sepolture antiche e medievali.<br>A pochi metri dalla Cattedrale, sotto la chiesa del Purgatorio, è la grotta di S. Cleto, cisterna di terme romane del I-II secolo d.C.