La Cattedrale di Matera è stata progettata dal primo arcivescovo della nuova diocesi, perchè la città fosse degna della nuova situazione religiosa ed amministrativa, infatti, nel 1203 si decise di unire la diocesi di Matera a quella di Acerenza.

La nuova chiesa fu costruita su una preesistente, quella di Santa Maria di Matera o, secondo altri, Santa Maria d'Episcopio. La costruzione della Cattedrale, in stile romanico-pugliese, iniziò nel 1230 e terminò nel 1270: a testimoniare la data del termine dei lavori, vi è un'iscrizione sull'architrave della porticina, che dà l'accesso al campanile, dove si legge "Mille ducentus erat annus septuagesimus dum fuit completa domus spectamine laeta" ovvero "Correva l'anno 1270 quando, bello a guardarsi, fu completato questo tempio". Della Chiesa precedente rimangono pochissime testimonianze, tra cui una scultura di un cavaliere (identificato da sempre con Sant'Eustachio,sul rosone del lato sud della Cattedrale) ed un affresco, detto della "Madonna della Bruna", sul primo altare della navata sinistra.

La facciata, monocuspidata ed a salienti, è rivolta a Est. Si nota il bellissimo rosone, simbolo della ruota della vita o delle stagioni, sostenuto da telamoni e sormontato da San Michele Arcangelo; sull'architrave della porta d'ingresso vi è la statua policroma della Madonna con il Bambino e, ai lati, San Pietro e San Paolo, opera di Altobello Persio e, ai lati dei due santi, vi sono Sant'Eustachio da una parte, e dall'altra, Santa Teopista. Sul lato Sud vi sono altre due porte d'ingresso, la prima detta di Abramo, poichè sull'architrave si trova la figura dello stesso e la seconda porta è detta dei "leoni", proprio per la presenza di questi due animali in tufo; a Nord, invece, vi sono la porta del "serpente" murata e quella delle "campane". Il campanile è a base quadrangolare ed è alto 52 metri, a tre piani con bifore.

La pianta è a tre navate, a forma basilicale, con cupola a tamburo, mascherata all'esterno da un tiburio; le colonne hanno diversi tipi di capitelli: questa caratteristica dimostra che la Chiesa ha subito molti rifacimenti, soprattutto tra il XVII e XVIII secolo, che si sono sovrapposti allo stile originario romanico-pugliese.

Infatti, da recenti restauri, sulla parete destra, di fronte all'immagine della Madonna della Bruna, dove era notevole la presenza di stucco barocco poi crollato, sono stati individuati affreschi del XIII e XIV secolo, che hanno come soggetto il Giudizio Universale.

Degni di nota sono: la Cappella dell'Annunziata opera di Altobello Persio (1544); il dipinto dell'altare maggiore "Cona Grande" opera di F. Santafede, sistemato da Giulio Persio; il coro ligneo realizzato da G. Tantino di Ariano Irpino (XV secolo); la Cappella del Santissimo Sacramento; la tela dell'altare di Sant'Anna; l'altare di San Giovanni da Matera con le reliquie del santo nell'urna; la Cappella del Presepe, opera di Altobello Persio e Jacopo Sannazzaro da Alessano del 1534; l'altare della Madonna della Bruna, con l'affresco del XIII secolo. Nel "Tesoro" si conservano una croce pettorale in argento (enkolpion), una piccola mitra trecentecsa, alcuni calici in oro e reliquiari di epoca rinascimentali e diversi libri corali miniati.