Fu costruita in stile romanico tra il 1087 e il 1100, durante la dominazione normanna. L'edificazione della basilica è legata alle reliquie di san Nicola, traslate, per la parte più appariscente da sessantadue marinai baresi dalla città di Myra, in Licia, e giunte a Bari il 9 maggio 1087. La basilica, considerata uno dei prototipi delle chiese romanico-pugliesi, sorge isolata a poca distanza dal mare.

Nell'abside centrale degno di nota è il pavimento con tarsie marmoree e con motivi orientaleggianti dei primi decenni del XII secolo assieme alla vigorosa sedia episcopale marmorea del 1105 e anche al monumento di Bona Sforza, regina di Polonia, di scultori del tardo Cinquecento.

Nell'altare dell'abside destro è presente un trittico di Andrea Rico da Candia del XV secolo; nella parete retrostante sono vari resti di affreschi trecenteschi. Sulla destra il ricco altare di San Nicola, in lamina d'argento sbalzato del 1684. Nell'abside sinistro campeggia una pala d'altare raffigurante la Madonna col Bambino in trono e i santi Giacomo, Ludovico, Nicola di Bari e Marco, sovrastata una cimasa che raffigura il Cristo in pietà fiancheggiato dai santi Gregorio e Francesco eseguita da Bartolomeo Vivarini nel 1476.

Il ciborio soprastante l'altare, realizzato prima del 1150, è il più antico della Puglia. Quattro colonne di marmo antico, le antistanti in breccia rossa, le posteriori in breccia viola, sostengono il baldacchino, composto da due tiburi piramidali a base ottagonale sovrapposti, sorretti da due serie di colonnine con articolati capitelli. L'elaborato riprende un motivo romano, affermando in tal modo esplicitamente richiami al classicismo. Splendidi sono i capitelli che concludono le colonne databili del terzo decennio del XII secolo.

Uno dei maggiori capolavori scultorei del romanico pugliese è conservato all'interno della basilica: si tratta di una cattedra episcopale realizzata al termine dell'XI secolo. La cattedra è ubicata dietro al ciborio, al centro del presbiterio e del mosaico che la riveste. Caratterizzata da un'ornamentazione molto curata, operata in parte a niello, ha il sedile elegantemente traforato negli alti braccioli, sostenuto da espressive figure in altorilievo e a tuttotondo, i telamoni. Sul dorso ci sono due leonesse intente a sbranare due uomini.

Due scaloni al termine delle navate laterali conducono nella cripta triabsidata, vasta quanto il transetto e sostenuta da 26 colonne varie abbellite da capitelli romanici. Sotto l'altare centrale della cripta riposa il corpo di san Nicola. Uno degli absidi laterali è destinato al culto ortodosso. La zona dell'altare dove riposano le reliquie del santo è rivestita da un mosaico pavimentale di eccezionale ricchezza di materiali proveniente da diverse aree geografiche.