Fu fondata nel 1034 dall'arcivescovo Bisanzio, eretta per volontà del suo successore Nicola e completata nel 1064 al tempo di Andrea II, contestualmente al trasferimento a Bari del seggio episcopale di Canosa, la più antica città cristiana della Puglia, decaduta ad opera dei Saraceni dell'Emirato barese.
Il nuovo edificio fu dedicato a San Sabino, vescovo di Canosa nel VI secolo, del quale in quegli stessi anni, secondo la tradizione, furono trasferite a Bari le reliquie. In precedenza la Cattedrale era dedicata alla Vergine Odegitria.
La cattedrale era una basilica a tre navate divise da colonne di reimpiego, sopraelevata di cinque metri rispetto alla precedente chiesa paleocristiana, i cui resti sono stati inglobati sotto il pavimento della cattedrale, poggiato su una struttura ancor oggi visibile corrispondente all'antica confessio.
Tra 1034 e 1066, protomagister della fabbrica è Acceptus, il primo grande scultore pugliese, al quale si devono le cornici dei cinque portali, vari capitelli ed un ambone, commissionato dal vescovo Andrea II e ricostruito nel 1955. Della fabbrica del Mille resta parte della confessio, riconoscibile nell'ambiente sotterraneo, diviso in tre navate, coperto da volte a crociera e preceduto da un atrio coperto da crociere senza sottarchi che si addossano sulla parete trasversale che chiude il complesso a ovest e proseguono verso nord e sud formando un corridoio che in origine metteva tale ambiente in comunicazione con l'esterno. Su questo ambiente si elevava la navata spartita dai colonnati, rimaneggiata nella successiva ricostruzione del XII secolo.
Nel 1156, quando la Cattedrale fu danneggiata gravemente dall'azione punitiva di Guglielmo il Malo.
Durante l'episcopato del vescovo Rainaldo (1178-1188) iniziò il restauro della fabbrica, che fu consacrata solennemente nel 1292. Rispetto alla prima basilica la nuova fabbrica si dotò di matronei limitati a solai lignei con trifore aperte sulla navata centrale, ballatoi pensili per la circolazione nei piani alti, e dell'impostazione della cupola, conservando le pareti d'ambito e le colonne ricollocate su un nuovo muro continuo di fondazione della chiesa di Bisanzio. Il transetto fu ricostruito estendendosi al di là della larghezza delle navate ed inglobando le absidi laterali, che affiancarono la grande abside centrale probabilmente già esistente e le torri laterali, su modella della basilica nicolaiana.
Nel 1267 un terremoto abbatté la torre N-E, ricostruita agli inizi del Trecento, e provocò vari danni ai quali pose rimedio l'arcivescovo Romualdo Grisone che provvide anche alla trasformazione della facciata con l'inserimento del rosone, e, forse, con l'aggiunta delle arcate cieche sulle fiancate laterali.
Nel 1613 crollò la torre S-E, non più ricostruita.
All'architetto napoletano Vaccaro si deve la trasformazione in chiave neobarocca dell'interno, poi completamente cancellata dai restauri degli anni Trenta del Novecento.
La facciata esterna è cuspidata con spioventi laterali e coronamento ad archetti pensili che poggiano su mensole antropomorfe e zoomorfe (XII-XIII sec.). È tripartita da semipilastri addossati e con tre portali che testimoniano le modifiche del XVIII secolo. Il portale centrale è affiancato da colonne con capitelli corinzi che sorreggono un cornicione aggettante con dentellatura. Un'edicola con l'Assunta sovrasta il cornicione affiancata dalle statue dei due patroni della città, s. Nicola e s. Sabino. Una bifora con colonna tortile al centro sovrasta il portale. Il rosone, recentemente ricostruito, è composto da una cornice a grani di rosario e archivolto costituito da elementi vegetali e sculture di animali. In basso e in alto rispetto al rosone ci sono 4 monofore delimitate da 2 fasce decorative. La facciata è conclusa in alto da un oculo. I portali laterali, affiancata da plinti con colonne che reggono un timpano spezzato, sono simmetrici a quello principale. Sul primo pilastro laterale a sinistra della facciata, si può notare l'attacco di un arco, forse traccia di un porticato.
La facciata N del transetto presenta nelle lunette degli archi ci sono finestre transennate mentre nel registro superiore bifore. Il rosone è recente. La parete absidale con arcate cieche è compresa fra due campanili, al centro una finestra del XII-XIII sec. incornicata da un arco sorretto da 2 elefanti stilofori.
I lavori di risanamento compiuti a partire dal 1966 al di sotto della navata centrale della cattedrale romanica hanno portato al rinvenimento di una serie di evidenze archeologiche che testimoniano lo sfruttamento dell'area in un vasto arco di tempo.
Le indagini archeologiche condotte a più riprese nel sottosuolo del succorpo hanno messo in luce i resti di un grande edificio di età romana con muratura a grandi blocchi e articolato in diversi vani, uno dei quali lungo ben 22 metri e largo circa 3 metri; i resti di una pavimentazione musiva con decorazione geometrica a cerchi allacciati formanti rosette a sei petali, datato alla prima metà del I secolo d. C. Reimpiegata negli ambienti di fase successiva è stata rinvenuta una epigrafe latina iscritta su una lastra di rivestimento in marmo di una base perduta. L'iscrizione si data alla seconda metà del II sec. d.C. e menziona un Augustale a cui viene riconosciuto dall'ordine dei decurioni il bisellium, testimoniando il funzionamento della vita istituzionale e l'esistenza nella città di un edificio per gli spettacoli.
In età tardoantica, probabilmente a partire dal V secolo, fu edificata, sui resti dell'edificio romano, una grande basilica a tre navate, con abside e pavimenti a mosaico policromo a motivi geometrici.
Fu questa la più antica cattedrale, rimasta in uso anche in età altomedievale, citata da una fonte del 1028 come S. Maria que est episcopio. Frammenti della decorazione pittorica delle pareti della Basilica si conservano negli ambienti laterali del succorpo. La basilica era rivestita da un pavimento musivo, al centro del quale campeggia un grande disco, entro cui sono situati un elemento quadrato con un motivo a stuoia e altri elementi quadrangolari, collegati da un nastro. Il tappeto è chiuso ad E da una tabula ansata con una iscrizione in latino in cui si ricorda un certo Timoteo che, durante l'episcopato di Andrea, fece realizzare parte della pavimentazione per sciogliere un voto, Il mosaico, attribuito al pieno VI secolo, si sovrappone a resti frammentari di fasi precedenti del piano pavimentale.

Data ultimo aggiornamento: 24/09/2018