Esempio notevolissimo dell'architettura romanica pugliese, la basilica domina la corte del Catapano, il funzionario che curava gli interessi dell'impero d'Oriente in Puglia tra il X e il XII secolo; alcuni storici ritengono che la chiesa abbia inglobato l'edificio dove l'ufficiale risiedeva, come confermerebbe una delle torri che affiancano la facciata.<br>La basilica fu iniziata sotto il principe normanno Ruggero I d'Altavilla all'indomani dell'arrivo a Bari delle spoglie di S. Nicola, provenienti da Mira in Asia Minore (1087); nel 1197 la chiesa era consacrata, ponendosi come la prima di tipo romanico che documenti influenze stilistiche provenienti dall'Occidente e non dalla tradizione orientale bizantina.<br>La facciata, dalle linee semplici, è tripartita da lesene impostate su colonne, coronata dal tipico motivo romanico degli archetti e aperta in alto da monofore, bifore e da una finestra circolare. Dei tre accessi in basso, che evidenziano la presenza di altrettante navate interne, il portale centrale è arricchito da un protiro con colonne poggianti su tori ai quali dopo il 1700 furono tolte le coma dorate; due torri racchiudono il prospetto. Tutti questi motivi avvalorano l'ipotesi della presenza di maestranze provenienti dal Nord Italia e depositarie di tecniche e stilemi nuovi per la Puglia bizantina del XII secolo.<br>Di notevole interesse risultano i fianchi della basilica, scanditi da arcate sormontate da esaforati e aperti da portali con ricche decorazioni scultoree; in particolare, quello della terza arcata sinistra rappresenta scene cavalleresche, ma soprattutto due figurazioni di mesi, motivo caro all'arte medievale dell'Italia centro-settentrionale (Toscana, Piemonte).<br>Rispetto agli accenti bizantini molto diffusi nell'architettura pugliese medievale, il programma di 'latinizzazione' si rivela in S. Nicola particolarmente nell'impianto del severo e suggestivo interno, a tre navate con matroneo e transetto dotato di tre absidi; latino è, ad esempio, il motivo delle volte a crociera nelle navate minori, mentre la copertura a capriate lignee, di tradizione romanico-lombarda o toscana, della nave centrale risulta oggi nascosta da un controsoffitto barocco con pitture e ricca doratura; il permanere di motivi bizantini è riscontrabile verso la zona dell'altare, dove una sorta di iconostasi divide il presbiterio dalla nave centrale, interrotta da due archi di sostegno che da metà '400 affiancano le colonne. Nell'abside centrale, il ciborio del 1150, che sovrasta l'altare, è il più antico della regione; la retrostante cattedra marmorea del vescovo Elia (XII secolo) è tra le più espressive sculture medievali pugliesi, nelle quali i motivi nordici sono intrisi di un realismo del tutto nuovo per le aree meridionali.<br>L'abside è occupata dal sepolcro della regina Bona Sforza, di fattura napoletana del tardo '500. Nell'abside sinistra è un polittico (1476) di Bartolomeo Vivarini; nel transetto destro il secentesco altare argenteo di S. Nicola. Due scale al termine delle navate laterali danno accesso alla cripta, consacrata nel 1089, che occupa lo spazio del presbiterio della chiesa superiore. Le 28 colonne che la affollano culminano in capitelli romanici e bizantini, in una singolare commistione tra arte greca e arte latina o occidentale; l'altare al centro racchiude le preziose reliquie di S. Nicola, molto venerate nel mondo cristiano sia orientale sia occidentale (questo spiega la presenza di una cappella adibita al rito greco-ortodosso). L’icona bizantina sull'altare risale al 1319 e venne donata dal re serbo Urosio II.