Sull'area dell'antico monastero benedettino di Sant'Eustachio, protettore della città, dove già tra il 1093 e il 1094 aveva soggiornato papa Urbano II, la cattedrale fu edificata a partire dal 1230, alcuni anni dopo che papa Innocenzo III aveva elevato la città di Matera al rango di arcidiocesi in unione con Acerenza; fu eretta per volere dell'Imperatore Federico II di Svevia, Imperatore del Sacro Romano Impero e Conte di Matera. Per fare in modo che il nuovo tempio dominasse con la sua mole le costruzioni circostanti e le due vallate sottostanti dei Sassi, fu necessario rialzare la base rocciosa di oltre sei metri.

L'interno è a croce latina ed a tre navate, con quella centrale che si eleva sulle altre, che sono divise tra loro da arcate a tutto sesto sostenute da dieci colonne sormontate da capitelli in pietra; ha subìto notevoli trasformazioni a partire dal 1627 con l'aggiunta di stucchi e decorazioni, e nel 1776 i rivestimenti di cornici e stucchi furono ricoperti di un velo di oro. La navata centrale è illuminata da 10 finestre (cinque per fianco), con il soffitto a capriate ricoperto nel 1719 da un controsoffitto ligneo su cui nel XIX secolo furono inserite tre tele dipinte dal calabrese Battista Santoro.

Di rilievo è un affresco bizantino risalente al 1270 della Madonna della Bruna con il Bambino benedicente con due dita, attribuito a Rinaldo da Taranto e ubicato sull'altare della prima campata della navata sinistra detto "della Bruna". Il secondo altare della navata sinistra è dedicato a San Giovanni da Matera e vi è un sarcofago contenente le sue spoglie, mentre sul terzo altare, detto di Sant'Anna, vi è una tela di ottima fattura del 1633 opera del frate Francesco da Martina. Dopo la cappella del Sacramento vi è la cappella rinascimentale dell'Annunziata realizzata da Giulio Persio, con volta a cassettoni e pareti a nicchie. In fondo alla navata c'è la cappella dove è situato il presepe in pietra dura realizzato dagli scultori Altobello Persio e Sannazzaro di Alessano tra il 1530 e il 1534, una delle sue opere più imponenti, che richiama diversi elementi propri della città di Matera. Dello stesso Altobello Persio è anche un ricco dossale di altare in pietra con sculture, risalente al 1539, posto in fondo al transetto sinistro.

Sulla prima porta della navata destra si trova una Madonna delle Grazie tra i santi Ilario e Giovanni da Matera, opera di Domizio Persio risalente al 1592, mentre sulla porta dei leoni è una tela di Carlo Rosa del 1652 raffigurante San Gaetano. Al terzo altare destro si trova un Crocifisso seicentesco in legno dipinto, e sull'ultimo altare un Polittico di Vito Antonio Conversi. Infine a destra dell'ingresso principale vi è il Giudizio Finale, pregevole affresco risalente alla fine del XIII secolo emerso durante alcuni lavori di restauro, unico esempio superstite dell'originaria decorazione pittorica, eseguito da Rinaldo da Taranto.