La cattedrale di Barletta, dedicata a Santa Maria Maggiore è il risultato di numerose sovrapposizioni di edifici di culto, risalenti ad un periodo compreso tra la fine del IV secolo a.C. e l'inizio del III secolo a.C., periodo a cui risalgono le tombe a grotticella, al cui interno sono state riportate alle luce scheletri umani e corredi funebri.
La costruzione ipogea si ipotizza sia stata anticamente un antico tempio pagano dedicato al dio Nettuno.
Al VI secolo risale la costruzione dell’antica basilica paleocristiana, con impianto a tre navate, terminanti in un'unica abside centrale rivolta ad est, i cui resti sono visibili ad oltre cinque metri sotto il livello dell'attuale duomo.
Nel 747, seguirono i lavori di rifacimento della chiesa dedicata a Santa Maria de Auxilio, al termine dei quali la struttura religiosa presentava un impianto a croce latina, retta da dieci pilastri.
Tra il 1147 e il 1153 furono realizzati i lavori di costruzione della chiesa romanica, in sovrapposizione alla chiesa di Santa Maria de Ausilio, ad opera del maestro Simiacca.
La chiesa era divisa in tre navate separate da due file di sei colonne e altrettante file di pilastri per fila, sulle si apriva l'antica copertura.
Nel 1234, Federico II commissionò i lavori di ampliamento, al termine dei quali la chiesa aveva due campate in aggiunta alle precedenti, delimitate da pilastri quadrilobati, terminanti con tre absidi semicircolari.
A questo periodo risale anche la costruzione del campanile collegato alla chiesa ed aperto nella parte bassa da un solo fornice.
La cattedrale di Santa Maria Maggiore è situata secondo un orientamento est-ovest, con il deambulatorio gotico rivolto verso est, e l'accesso principale verso Palazzo Santacroce.