Такое обилие чудес от мощей Святителя Николая и данное ранее обещание моряками расположили барян построить новую каменную церковь в честь Святителя Николая. Начались работы по перестройке здания Corte del Catapano, которое тогда же было пожертвовано герцогом Рожером с тем, чтобы оно обращено было в храм Святителя Николая. (Вероятно, во время этой перестройки вышеупомянутая церковь во имя св. Евстахия была уничтожена, так как в непродолжительном времени мощи св. Николая перенесены были во временную церковь, в коей находился алтарь во имя св. первомученика Стефана.) Для надзора за ходом постройки храма и для сбора пожертвований избран был упомянутый выше игумен Бенедиктинского монастыря Илия. Через два года, в 1083 году, постройка храма была окончена. К этому же времени была приготовлена для мощей Святителя серебряная рака, украшенная драгоценными камнями.
По построении церкви, клир и народ Бар-града отправили в Рим к папе Урбану II просьбу, чтобы он со своим священным собором пришел в Бар-град, освятил новую церковь во имя Святителя Николая и своими священными руками положил в новую раку честные мощи Угодника Божия. Папа Урбан II с радостью согласился на исполнение этой благочестивой просьбы и немедленно со своим собором прибыл в Бар-град. Здесь он переложил мощи в новую раку и перенес их в новосозданную церковь святителя Николая и поставил в алтаре. В новой же церкви был поставлен и гроб, в котором ранее лежали мощи святого Угодника и в который была отделена и положена часть его мощей. Затем была освящена и церковь в честь Святителя Николая. Освящение это последовало 1 октября, причем освящена была нижняя церковь, в которой и до сих пор находятся мощи св. Угодника. Верхняя же церковь могла быть освящена не ранее как 22 июня 1197 года епископом Вюрцбургским Конрадом, с разрешения папы Целестина III (1196–1198).
Некоторое время спустя Святитель Николай явился во сне одному благочестивому монаху и сказал ему: «Благоволением всесильного Бога я пришел к вам в город Бари; теперь я хочу, чтобы мощи мои были положены под престолом». Воля святого Угодника немедленно была исполнена, и тело его положено под престол, где оно находится и в настоящее время.
Вот вкратце история новосозданной церкви, в которой положены и теперь почивают мощи Святителя Николая. После смерти архиепископа Барского Урсона, последовавшей незадолго до освящения нижней церкви во имя св. Николая, в преемники ему, согласно общему желанию, поставлен был папой Урбаном II 30 сентября 1089 года игумен Илия, которому тогда же папа дал титул «архиепископа Барского, игумена церкви св. Николая». При нем устроен был близ церкви госпиталь или приют для помещения бедных странников. Эта странноприимница существует и поныне. Иностранцам позволяется оставаться в ней бесплатно три дня, туземцам же богомольцам – один день. При нем же установлено совершать ежегодно 9 мая крестный ход по городу.