Православный приход в городе курессааре (Аренсбург) был основан в 1747 году по приказу императрицы Елизаветы. Богослужения русского прихода проходили в крепости Курессааре в деревянной церкви, освящённой в честь Святого Николая в 1750 году. После завершения строительства нынешней каменной церкви в 1790 году, деревянная церковь была снесена. В 1847 году были проведены масштабные работы по перестройке этой церкви, представляющей собой оштукатуренное изнутри и снаружи трёхнефное здание с башней и колокольней.

В 1846 году, в помощь священнику Панову, в город Курессааре, для проведения богослужений на эстонском языке, был отправлен выпускник Псковской духовной семинарии Яков Бойков, изучавший в семинарии эстонский язык. В 1846-1847 годах Бойков служил в приходе Курессааре помошником священника, затем был священником на острове Муху, а в 1858 году вновь вернулся в Курессааре. Для проведения богослужений на эстонском языке в восточной части храма был установлен дополнительный алтарь, который был освящён в 1879 году в честь Вознесения Господня.

В период советской власти число прихожан начало быстро сокращаться. Если до 1930 года их число составляло 1645 человек, то к 1970 году численность прихожан сократилась до 348. Число прихожан начало расти на переломе 1980 - 1990-ых годов, с наступлением свободы вероисповедания в период так называемой "поющей революции". В начале XXI  века в церкви был проведён ремонт.