В тот же самый день, еще прежде солнечного восхода, исцелился один юноша, пять лет одержимый бесом глухим, немым и слепым. В субботу, в десятом часу, по возвращении святого Николая, исцелилось одиннадцать недужных.

Такое обилие чудес от мощей святителя Николая и данное ранее обещание моряками расположили барян построить новую каменную церковь в честь святителя Николая. Начались работы по перестройке здания Corte del Catapano, которое тогда же было пожертвовано герцогом Рожером с тем, чтобы оно обращено было в храм святителя Николая. Вероятно, во время этой перестройки вышеупомянутая церковь во имя святого Евстахия была уничтожена. В скором времени мощи святителя Николая перенесены были во временную церковь, в которой находился алтарь во имя святого первомученика Стефана. Для надзора за ходом постройки храма и для сбора пожертвований избран был упомянутый выше игумен бенедиктинского монастыря Илия. Чрез два года, в 1089 году, постройка храма была окончена. К этому же времени была приготовлена для мощей Святителя серебряная рака, украшенная драгоценными камнями.

По построении церкви клир и народ Бари отправили в Рим к папе Урбану II просьбу, чтобы он со своим священным собором пришел в Бари, освятил новую церковь во имя святителя Николая и своими священными руками положил в новую раку честные мощи угодника Божия. Папа Урбан II с радостью согласился на исполнение этой благочестивой просьбы и немедленно со своим собором прибыл в Бари. Здесь он переложил мощи в новую раку и перенес их в новосозданную церковь святителя Николая и поставил в алтаре. В новой же церкви был поставлен и гроб, в котором ранее лежали мощи святого угодника. В него была также отделена и положена часть его мощей. Затем была освящена самая церковь в честь святителя Николая. Освящение это последовало 1 октября, причем освящена была нижняя церковь, в которой и до сих пор находятся мощи святого угодника. Верхняя же церковь была освящена только через сто лет.

Некоторое время спустя святитель Николай явился во сне одному благочестивому монаху и сказал ему: «Благоволением всесильного Бога я пришел к вам в город Бари. Теперь я хочу, чтобы мощи мои были положены под престолом». Воля святого угодника немедленно была исполнена, и тело его положено под престолом. Там оно находится и в настоящее время.

Вот вкратце история новосозданной церкви, в которой положены и теперь почивают мощи святителя Николая.

После смерти архиепископа Барского Урсона, последовавшей незадолго до освящения нижней церкви во имя святителя Николая, в преемники ему, согласно общему желанию, поставлен был папой Урбаном II 30 сентября 1089 года игумен Илия. Папа тогда же дал ему титул «архиепископа Барского, игумена церкви св. Николая». При нем устроен был близ церкви госпиталь и приют для помещения бедных странников. Этот странноприимный дом существует и поныне. Иностранцам позволяется оставаться в ней бесплатно три дня, туземцам же богомольцам – один день. При нем же установлено совершать ежегодно 9 мая крестный ход по городу.

По смерти Илии, последовавшей в 1105 году, преемником его по управлению храмом святителя Николая был Евстафий, украсивший церковь мрамором и мозаикой. По смерти его избран был на его место приор монастыря Всех Святых Melo, и с этого времени настоятели храма святителя Николая Чудотворца именуются приорами (gran priori). Папа Урбан II, почти вслед за положением в церкви мощей святителя Николая, изъял ее из зависимости от местной епархиальной власти и подчинил ее непосредственно папскому престолу, что подтверждено было и папой Пасхалием II (1099– 1118).