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 da sessantadue marinai baresi dalla città di Myra, in Licia, e giunte a Bari il 9 maggio 1087. Le reliquie vennero ospitate provvisoriamente presso il monastero di san Benedetto retto dall'abate Elia, il quale promosse subito l'edificazione di una nuova grande chiesa per ospitarle. Fu scelta l'area che sino a pochi anni prima aveva ospitato il palazzo del catapano bizantino, distrutto durante la ribellione per le libertà comunali e che Roberto il Guiscardo aveva donato l'anno prima all'arcivescovo Ursone; i lavori furono avviati a luglio dello stesso anno. Il 1º ottobre 1089 le reliquie furono trasferite nella cripta della basilica da papa Urbano II giunto appositamente a Bari.

Ad ottobre del 1098 nella cripta della basilica ancora in costruzione si tenne il II Concilio di Bari, convocato dallo stesso Urbano II, al quale presero parte circa 185 arcivescovi, vescovi ed abati, oltre ad ecclesiastici di grado inferiore. La costruzione della basilica, frutto di almeno tre fasi successive, si concluse nel 1103 quando una pergamena parla della Basilica già constructa. La lapide di consacrazione del 1197 che alcuni interpretano come fine dei lavori era un atto devozionale dell'imperatore Enrico VI che, a ricordo del padre Federico Barbarossa, partiva per la Crociata chiedendo la benedizione di San Nicola.

La basilica, considerata uno dei prototipi delle chiese romanico-pugliesi, sorge isolata a poca distanza dal mare. La facciata a salienti, semplice e maestosa, è tripartita da lesene, coronata da archetti e aperta in alto da bifore e in basso da tre portali, dei quali il mediano, a baldacchino su colonne, è riccamente scolpito. Due torri campanarie mozze, di diversa fattura, fiancheggiano la facciata. I fianchi si caratterizzano per le profonde arcate cieche (sopra le quali corrono loggette a esafore) e le ricche porte. Arcate cieche in basso e bifore in alto animano le alte testate del transetto e la parete continua absidale, ornata al centro da un grande finestrone. L'interno presenta uno sviluppo planimetrico a croce latina commissa. Il corpo longitudinale è diviso in tre navate da dodici colonne di spoglio (sei per lato, con le prime quattro binate, cioè affiancate a coppie). Il ritmo della navata centrale, con copertura a capriate, è scandito da tre arconi trasversali, aggiunti nel XV secolo in seguito a un terremoto che aveva reso pericolante l'intera costruzione. Mentre i primi due si impostano sulle prime quattro coppie di colonne binate, l'ultimo arcone è retto da due massicci pilastri compositi, posti quasi a metà della navata stessa. Al di sopra degli archi c'è il piano del matroneo a trifore. Il soffitto è intagliato e dorato accompagnato con riquadri dipinti del XVII secolo. Tre solenni arcate su graziose colonne dividono la navata centrale del presbiterio. L'altare maggiore è sormontato da un ciborio del XII secolo. 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 una tavola con Madonna e Santi del 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 elaborati capitelli. Splendidi sono i capitelli che concludono le colonne databili del terzo decennio del XII secolo. Quelli anteriori recano figure angolari di angeli, quelli posteriori sono ornati, uno da figure di animali, l'altro da motivi vegetali.

Uno dei maggiori capolavori scultorei del romanico pugliese è conservato all'interno della basilica: si tratta di una cattedra episcopale (Cattedra di Elia) 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. Da un'iscrizione posta sul retro del sedile, che lega l'opera alla figura dell'abate Elia, arcivescovo di Bari e Canosa, si è fatto risalire il lavoro agli anni tra il 1098 e il 1105. Se tale datazione fosse accertata, la cattedra costituirebbe uno dei primi lavori del romanico pugliese. In realtà l'opera è da collocarsi più probabilmente nella prima metà del XII secolo per la vitalità e la maturità dei rilievi.