La Cattedrale fu fondata, come ricordava un'iscrizione sul fondo dell'arco trionfale della chiesa, nel 1073 dal normanno conte Pietro II, che la dedicò a San Pietro. Fu terminata solo nel 1295 e consacrata nello stesso anno.
E' di fattura romanico-pugliese, ma appare assai deteriorata da rifacimenti posteriori, da cui sono rimasti immuni in parte la facciata, l'abside ed i muretti dei matronei, visibili solo dall'esterno.
La facciata (XIII secolo) ha un portale assai ornato, a triplice fascia di tralci di foglione, con protiro sorretto da grifi su colonne di marmo, con capitelli a foglie di acanto mosse dal vento, di gusto bizantino. Gli archivolti dei portali laterali sono impostati su mensole a protome leonina. In alto si possono vedere i coronamenti ad archetti, due bifore e quattro monofore. Una finestra barocca sostituisce il rosone originario.
Nel fianco destro c'è un grande portale tra due colonne antiche, sormontate da due rozze sculture; a sinistra c'è un curioso bassorilievo raffigurante una giovenca e delle tavole.
Meglio conservata è la parete absidale ad arcate cieche con bella finestra e mensole con animali, tra due campanili quadrati di uguale altezza. Alla fine del '600 il campanile constava della sola torre di sinistra.
L'interno, basilicale a tre navate, è deturpato dal barocco. Si vedono qua e là i segni misteriosi dei Maestri Comencini: squadra, martello e compasso.
La cripta, deturpata dallo stile barocco, poggia su dieci colonne di breccia corallina, dal colore giallo e paonazzo. Vi si conservano le ossa ed alcune reliquie dei tre Santi ed il braccio di Santo Stefano. Nel centro è posto l'antico sepolcro dei Vescovi.
Verso la metà del '700 ed i primi dell'800 iniziarono i lavori di trasformazione dell'agile stile romanico in pesante barocco, sul modello della Basilica di San Pietro: fu demolito il tetto del matroneo, che rimase totalmente chiuso; furono aperte finestre sui fianchi della navata centrale; fu demolita la quinta posteriore, con taglio dei muri a partire dal centro del rosone della facciata; fu costruita la cupola e continuato il campanile in stile barocco. Davanti al protiro venne costruita una scalea per migliorare l'accesso alla cripta, posta alla base della scalea. Nell'interno fu eseguita la modificazione in stile barocco del cornicione e dei capitelli delle colonne. Il pavimento attuale della chiesa sembra sia stato sopraelevato su quello originario.
Ai lati del presbiterio c'è un bellissimo coro in noce massiccio, proveniente dalla Badia benedettina di Santa Maria dei Miracoli in Andria. Esso rappresenta la storia dell'Ordine benedettino dalle origini alla fine del Medioevo.
Esternamente alla cappella della navata destra della chiesa vi è un affresco, copia del Tiziano, rappresentante San Cristoforo, oggi quasi cancellato.