The Catholic complex in Tromsø is situated near the town square, in the middle of the Tromsø town centre. The bishop's palace (bishop's official residence) faces towards the street Storgata, while Our Lady Church lies adjacent to the street Grønnegata. In between these two structures lies a courtyard, which used to be the Chatolic schools. Originally, the Catholic bishop's palace was erected as a merchant's estate for the consul Th. B. Holst, around 1820-1830. The church was consecrated in 1861.

Our Lady Church is situated with the choir facing north and the town square entrance in the south. This is a somewhat unusual orientation. This rather small church is a long church with one nave that is clad with horizontal panelling. It also has windows that are capped with sharp arches. The church has two ridge turrets, one above the entrance with a steeple crown and a larger octagonal shaped-one above the choir. There are also two pinnacle-like structures - one on each side of the ridge turret above the entrance. The church is painted an ochre colour, while the details and cornice are painted brown. Clay tiles cover the roof.