Il 13 febbraio 1503 i tredici cavalieri italiani, al primo sorgere del sole, si recarono in Cattedrale ove, nelle mani di Prospero Colonna, davanti al Sacramento, giurarono di vincere o morire.

La storia della Cattedrale barlettana è legata a quella del Certame Cavalleresco. Per ricordare quel momento solenne, sul lato destro del Duomo, è ben visibile una epigrafe collocata in occasione del quarto centenario della Disfida: "Del gran capitaneo in Barletta nell'anno del Signore 1503 fu la gran vittoria et proprie in anno sexte indictionis", inoltre, all'interno di essa, è conservata l'effigie della Madonna della Sfida, dipinta nel 1387 da Paulus Serafini de' Serafinis ed originariamente dedicata alla Madonna dell'Assunta.

L'area dell'attuale cattedrale, adibita in epoca dauno - romana come area sepolcrale, fu utilizzata in età tardo antica per la costruzione di una grande basilica paleocristiana datata al VI secolo d.C. Al di sopra di questa chiesa si eleva l'attuale cattedrale.
È costituita da due parti architettonicamente e stilisticamente distinte, ma mirabilmente fuse.

La sua costruzione ebbe inizio nella prima metà del secolo XII. Le colonne lisce sono di foggia antica, con capitelli di diversa forma e stile, in parte antichi in parte coevi alla costruzione. Il matroneo è sostituito sulle pareti superiori della navata centrale dalle grandi bifore.

Nella prima metà del XIV secolo fu innestata la seconda parte dove furono alloggiate la cattedra, il pergamo e tre altari della distrutta Cattedrale di Canne. Lo stile qui si fa chiaramente gotico. Proseguono le tre navate romaniche, ma poggiano su pilastri squadrati con volte a crociera nella navata centrale e a botte nelle laterali. Le navate laterali sono ben più alte di quelle romaniche.

La chiesa in questa zona si "allarga" fino ad assumere una pianta trapezoidale, invisibile all'occhio. Il coro gotico con cui termina l'edificio, è costituito da una grande abside poligonale a cinque lati. La divisione in cappelle del deambulatorio è scandita anche all'esterno.

Le sculture della chiesa sono databili alla metà del XII secolo e sono quindi coeve alla costruzione. Il Campanile si eleva sul fianco nord, ha quattro livelli superiori all'arcone terreno, che oggi assolve la funzione di portale di ingresso al centro storico.