Баряне утешали плачущих мирян тем, что у них остается гроб святителя, полный святого мира, и икона его, от которой много получается исцелений, а сами поспешно отплыли от пристани. Баряне сознавались, что почти на 4 километра слышен был плач стоявших на берегу жителей Мир, и что многие из путешественников сами плакали, сочувствуя их горю.
Выехали из Мир баряне в апреле 1087 года. В первый день по выезде из Мир им помогал плыть домой попутный ветер. Но на следующий день подул северный ветер и повернул их корабль по направлению к городу Патары (родине святителя Николая). Баряне устрашились, думая, что угодник не хочет расстаться с берегами Ликии; вместе с тем они боялись преследования, потому что Патары находились недалеко от Мир. Поэтому путешественники, уже утомленные дорогой, причалили на время к пристани Макри. Здесь они стали рассуждать, отчего так мало подвинулись вперед во время трехдневного пути. Одни спрашивали, точно ли это мощи святителя Николая; другие боялись, что прогневали святителя смелым своим поступком; третьим, наконец, пришло на мысль, не взял ли кто из товарищей, по чувству усердия и веры, частицу мощей св. угодника. Тогда остановились на этой последней догадке, принесли Евангелие, и каждый из мореплавателей обязан был поклясться, что не похитил ни малейшей части мощей. Пятеро признались в этом проступке и отдали похищенные части. Тогда море успокоилось, и подул благоприятный ветер. Мореплаватели поняли, что их священный долг привезти в Бари драгоценный клад в целости, и с тех пор путь их продолжался счастливо.
Когда мореплаватели миновали залив Трахеи, одному из пловцов в глубоком сне явился святитель Николай и сказал: «Не бойтесь, я с вами! Чрез двадцать дней мы придем в город Бари». Проснувшись, моряк рассказал, что видел, товарищам, и они исполнились глубокой радости.
На дальнейшем пути произошла следующая удивительная вещь. Одна маленькая ласточка села на правом руле судна, на котором везли святое тело. Ходя по нему безо всякого страха, как будто была привычной жительницей его, она тихо вспрыгнула на руку одного из мореплавателей, который в то время правил рулем. Оттуда перелетела к месту, где покоилось святое тело и, напевая тихонько, носом своим клевала тот сосуд, в котором сокрыты были святые мощи. «Благосклонные братья! — замечает по поводу этого события современник события, западный писатель Никифор, оставивший нам рассказ о перенесении мощей, — сколь хвален всемогущий Бог, побуждавший к хвалению и почитанию Своего святого исповедника не только людей, но и немых животных. Ибо пение птицы было хвалением, а прикосновение клювом означало лобзание, которое она верно приносила святому телу. Напевая, она облетала каждое судно и всех людей и видна была всем, воздавая хвалу блаженства им за то, что они везли такого велелепного и дивного пастыря.
Исполнив долг своего послушания, она отлетела и скрылась из виду».
Наконец, после продолжительного путешествия, баряне 8 мая пришли в пристань святого Георгия, Христова мученика, отстоявшую на 8 километров от Бари. Отсюда они дали знать жителям города о скором прибытии в их город мощей знаменитого чудотворца Востока, а сами занялись приготовлением деревянного ковчега, в который и были положены мощи святителя.
Молва о прибытии мореплавателей с мощами великого чудотворца разнеслась по всему городу. На следующий день, 9 мая, на столь чудное и желанное зрелище стеклась огромная толпа народа. Духовенство барское в священных облачениях вышло навстречу принять тело святого угодника. Прибывшие сообщили своим согражданам, что они, когда брали тело святого, дали священный обет воздвигнуть ему достойную церковь на дворе господском, что называется Катапани, и теперь настаивают на исполнении ими их желания. По поводу этого произошло большое разногласие: одни (большинство) одобрили их обещание, другие же хотели, чтобы святитель Николай был погребен в городском соборе (епископии).
Желая мирным путем устранить такое разногласие, настоятель бенедиктинского монастыря, по имени Илия, уговорил возвратившихся мореплавателей перенести тело угодника в церковь его обители, пока будет строиться новая. Путешественники согласились на это, так как настоятель Илия слыл за человека благочестивого. Вокруг обители стали моряки с оружием в руках, страшась мести оставшихся недовольными тем, что соборное духовенство не успело опередить настоятеля Илию.