Non fu poi difficile al pio abate Elia ottenere dalla munificenza di Ruggero il Normanno, duca di Puglia, l'antica residenza dei governatori bizantini (Corte del Catapano) con le sue adiacenze per innalzarvi la nuova chiesa in onore di san Nicola. La costruzione procedette tanto rapidamente, che in due anni ne era già compiuta la cripta, che venne consacrata il 29 settembre 1089 personalmente dal papa Urbano II, il quale volle deporre con le sue stesse mani nell'urna sottostante l'altare le reliquie del glorioso taumaturgo, provvedendo altresì nella circostanza alla consacrazione episcopale dell'abate Elia, nominato arcivescovo di Bari. Ed ai piedi di quell'altare andò a pregare nel 1095 Pietro l'Eremita per il buon esito della crociata, lí pregò anche Boemondo d'Altavilla prima di partire per la santa impresa alla testa dei suoi valorosi guerrieri pugliesi, ed in quella stessa cripta ancora Urbano II tenne nel 1098 l'importante concilio in cui si trattò della riunione fra la Chiesa latina e la Chiesa greca. 

CULTO  Già intenso al principio del sec. VI il culto di san Nicola in Oriente ebbe ben presto la sua esaltazione in vari edifici sacri a lui dedicati; una grande chiesa in suo onore venne infatti innalzata a Costantinopoli. Patrono di Bari, di Venezia, di Merano di Ancona, di Sassari e di altre città italiane ed estere ultima delle quali è stata La Rioja nella Repubblica Argentina, nonché di regioni, come la Puglia e la Sicilia, e di intere nazioni, come la Russia e la Grecia, san Nicola viene variamente rappresentato, trovandosi in specie trasformato dal popolo in un vecchio munifico dalla lunga barba bianca, che porta doni ai bimbi buoni nella notte di Natale, divenuto nel folklore anglosassone Santa Claus (una corruzione di Sanctus Nicolaus.  Ancor oggi dalle ossa dei grande taumaturgo di Bari trasuda un liquido limpido e puro, detto «manna di san Nicola», a cui si attribuiscono poteri miracolosi, e che cominciò a stillare subito dopo il suo glorioso trapasso, trovandosi di ciò menzione presso tutti gli antichi scrittori e panegiristi, da S. Metodio, a san Teodoro Studita a Niceforo, e persino nella seconda Novella dell'imperatore Emmanuele Comneno. L'esistenza di varie altre reliquie di san Nicola in molte chiese a lui dedicate nel mondo, ponendo il problema della loro autenticità, ha fatto sorgere anche la questione se nel sarcofago di Bari siano contenuti tutti i resti ossei del santo vescovo, come affermavano alcuni autori sulla base di un decreto dell'8 aprile 1868 della S. Congregazione dei Riti; per cui nella notte tra il 5 ed il 6 maggio 1953 si procedette alla ricognizione canonica dei resti di san Nicola, effettuata da una speciale commissione designata, per disposizione di Pio XII, dalla stessa Congregazione dei Riti. Fu accertata così l'incompletezza dello scheletro del santo, le cui parti mancanti vennero poi esattamente precisate nello studio anatomico - antropologico eseguito nel 1957 dei resti esistenti nella tomba barese; ma mentre è dato pensare che qualche cosa possa pur essere rimasta nell'antico sepolcro di Mira, si devono altresì tener presenti anche quei resti che non è stato possibile attribuire ad alcuna parte dello scheletro del santo per la loro piccolezza e la loro forma, resti raccolti in due coppe d'argento giacenti nello stesso sarcofago marmoreo della cripta.  Il Martirologio Romano commemora san Nicola tanto il 6 dicembre suo dies natalis, quanto il 9 maggio giorno della traslazione delle sante reliquie a Bari.