La più antica notizia riguardante la diocesi di Trani è fornita da un atto di donazione dell' 834. Lo stesso documento fa esplicita menzione di una cattedrale dedicata a Santa Maria.
Dell'esistenza di una chiesa precedente a quella attuale si ha conferma in uno scritto risalente all' XI secolo relativo alla traslazione a Trani delle spoglie di San Leucio, vescovo di Brindisi, avvenuta dopo che nel 663, per la lotta tra l'imperatore Costante II e i Longobardi del ducato beneventano, questa città venne quasi completamente distrutta. Altre testimonianze dell'antica chiesa tranese possono essere riconosciute nei numerosi elementi lapidei di epoca alto-medievale riutilizzati nella fabbrica della cattedrale romanica. Non è privo di significato, inoltre, il fatto che la cripta longitudinale, che si estende al di sotto della navata centrale, abbia conservato l'antica intitolazione di Santa Maria.
La costruzione della cattedrale romanica, dedicata al giovane pellegrino greco di nome Nicola, che giunto a Trani vi morì nel 1094, ebbe inizio tré anni dopo questa data per volontà del vescovo Bisanzio e si protrasse per circa due secoli, mentre la torre campanaria, iniziata nella prima metà del '200, venne ultimata verso la metà del sec. XIV.
L'imponente edificio si sviluppa su due livelli con due cripte in corrispondenza della navata centrale e del transetto al piano inferiore, comprendendo un ipogeo collocato ancora più in basso nella zona presbiteriale. Per l'architettura, che si erge in riva al mare in un incomparabile scenario ambientale, per la ricca ornamentazione scultorea, per l'elegante e prezioso corredo decorativo nel quale si distinguono le porte bronzee di Barisano ed i resti del mosaico pavimentale, la cattedrale di Trani è tra i monumenti più importanti ed ammirati della Puglia. All'interno, la presenza di colonne binate tra la navata centrale e le laterali costituisce un elemento del tutto originale nell'architettura italiana del Medioevo ed ha portato alla formulazione di ipotesi di derivazione da modelli d'oltralpe, in particolare francesi.
Dopo il suo completamento, avvenuto tra fasi alterne con molte interruzioni, l'edificio venne accresciuto nel Quattrocento di nuove fabbriche, sul lato settentrionale; subì modifiche nell'apparato decorativo interno tra il XVII e il XIX secolo e probabilmente anche all'esterno, con la demolizione del portico antistante la facciata. Infine, tra il 1950-60 è stata ripristinata la configurazione originaria con la demolizione dei corpi aggiunti e la eliminazione della decorazione barocca dell'interno.
Gli ultimi restauri sono stati motivati dal manifestarsi di un diffuso stato di degrado particolarmente evidente nel sistema delle coperture e nelle strutture murarie. Tra i fenomeni più appariscenti in senso negativo risultavano lo scivolamento delle falde e la sconnessione del manto di tegole, con infiltrazione delle acque piovane; il degrado delle murature, in particolare all'interno, causato dall'azione combinata delle sostanze contenute in sospensione nell'atmosfera di origine marina, in presenza del microclima determinato dall'inerzia termica delle strutture di notevole spessore. Particolarmente accentuata la presenza di umidità derivante da fenomeni di condensazione nella chiesa superiore e dalla mancanza di un adeguato isolamento della pavimentazione nelle cripte sottostanti.