[1][2][3] The yellow, wooden cathedral was built in a long church format and the Gothic Revival style in 1861 by the architect Christian Heinrich Grosch.

It is situated in the middle of the city of Tromsø (on the island of Tromsøya) on a site where in all likelihood, there has been a church since the 13th century.

This church is mentioned several times in the Middle Ages as "St. Mary's near the Heathens" (Sanctae Mariae juxta Pagano).

The 1803 church building was relocated to an area a few hundred metres south of the city boundary.

Then in the early 1970s, it was moved again to the present Elverhøy Church site further up the city’s hills.

Stained glass windows in the front of the church, designed by Gustav Vigeland, were installed in 1960.

The oldest mechanical organ located at the gallery was built in 1863 by Claus Jensen and restored in 2013–2014.