W spisanym około 565 roku żywocie archimandryty Mikołaja z klasztoru Syjon (Vita Nicolai Sinonitae) pojawiła się opowieść o tym, że ów pobożny mnich, wyruszając na pielgrzymkę do Jerozolimy, odwiedził Mirę. Tam modlił się w bazylice poświęconej świętemu biskupowi Mikołajowi. Z tekstu wynikało, że biskup był uważany za męczennika, a jego zwłoki przeniesiono wiele lat po męczeństwie z miejsca śmierci do bazyliki, gdzie zbudowano martyrion. Natomiast Prokopiusz z Cezarei w dziele O budowlach, powstałym w latach 553–555, zanotował w księdze drugiej, że cesarz Justynian wybudował w Konstantynopolu kościół pod wezwaniem świętych Priskosa i Mikołaja. Nie jest jednak jasne, któremu Mikołajowi dedykowano nową świątynię.
Od VI do drugiej połowy VIII wieku nie zapisano żadnych nowych informacji o Mikołaju. Dopiero w aktach drugiego soboru nicejskiego z 787 roku zanotowano, że jeden z archidiakonów miał sen, w którym ukazał się Święty Mikołaj. Diakon sądził, że przemówił do niego patriarcha Konstantynopola, jednak biskup Miry Teodor sprostował, że chodziło o biskupa jego miasta.
Z początkiem IX wieku w źródłach pojawia się coraz więcej postaci o imieniu Mikołaj, co świadczyć może o rosnącej popularności kultu świętego.