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

Параскева Николау больше в Варну не возвращался, но, несмотря на это, выполнил данный обет. Он выслал средства и поручил Панко Георгиеву потратить их на строительство церкви и больницы. Строительство началось в 1859 г. и продолжалось шесть лет. Неизвестно, когда точно был освящен храм и когда состоялась первая служба. В документах также не указано, когда появился иконостас. Достоверно известно лишь то, что его привезли в церковь готовым, а иконы подносили в дар зажиточные миряне. Лишь в 1906 г. здесь начинают проводить богослужения болгарские священники. До этого времени церковь Святого Николая считалась греческой. Обострение греко-болгарских отношений в городе пришлось на 1906 г., кода в Варну приехал новый греческий митрополит Неофит. Болгары, вдохновленные обществом "Родолюбец" ("Патриот"), не дали владыке даже сойти с корабля. На следующий день, 4 июня, "взяли" церковь Святого Николая. А 9-го числа была отслужена первая болгарская литургия. Долгое время стены храма были нерасписанными. Лишь в 1961 г. под руководством профессоров Николы Кожухарова и Димитра Гюдженова их расписывают, и храм приобретает свой сегодняшний облик. Художники Петр Джамджиев, Петр Михайлов и студенты Художественной академии около месяца трудились над росписью.

Церковь Святого Николая является единственным морским храмом в Болгарии. В 1927 г. два болгарских капитана отвезли к гробу Господню икону из церкви, освятили ее и привезли обратно. И тогда этот храм записали в церковных книгах как морской. Здесь до 9 сентября варненские моряки давали присягу. Осенью 2000 г. по идее Димитра Стайкова, механика Болгарского морского флота с многолетним стажем и при содействии морских учреждений у входа в храм устанавливают еще один символ морячества - корабельный якорь. Его сняли с корабля "Богдан" перед тем, как отправить на утилизацию.

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