Первые упоминания о церкви Святого Николая в Улцине датируются концом XIX столетия. Однако история появления церкви началась ещё раньше – прежде на месте строения храма находился монастырь, основанный в XV веке. Незадолго до момента, когда Улцинь был освобождён от турок, в 1869 году православные верующие Улциня выстроили недалеко от Белой Горы собственный храм. Турецкий закон гласил, что ни одно возводимое в городе здание не могло превышать по высоте минарет мечети. Строители церкви Св. Николая поступили очень находчиво: они построили просторную церковь, врытую вглубь земли. Таким образом, закон не был нарушен. Несколько лет церковь служила мечетью, но с 1890 года, после перестройки, она вновь стала православным храмом Святого Николая. Посвящена воинам, погибшим за независимость Черногории.