Prawosławna cerkiew została zbudowana w 1858 r. Znajdują się w niej relikwie św. Mikołaja Cudotwórcy. Jest to prawdopodobnie jedyna świątynia w kraju ufundowana w całości przez jedną osobę - zbudowano ją dzięki greckiemu kupcowi Paraskeva Nicolaou. Przed cerkwią można obejrzeć poświęcony mu pomnik.
Paraskeva Nicolaou postanowił wznieść świątynię w podzięce Bogu za uratowanie życia. Mówi się, że gdy płynął do Odessy, na Morzu Czarnym rozpętał się gwałtowny sztorm. Wówczas przerażony kupiec zaczął modlić się do św. Mikołaja i zadeklarował, że jeśli tylko wyjdzie z tego żywy, ufunduje kościół i szpital na cześć świętego. Mimo że sam nie powrócił już do Warny, zobowiązał wykonawców swojego testamentu, by po jego śmierci zbudowano obydwie instytucje.
Obecnie co roku 6 grudnia, czyli dzień poświęcony św. Mikołajowi, na cerkiewnym placu odbywa się uroczysta ceremonia, podczas której kapłan błogosławi żeglarzy i marynarzy.