The church's footprint and cross section are based on the medieval basilica church model with a tall nave, lower aisles and clerestory windows. However, the recessed clerestory windows are a modern interpretation that generously flood the nave in daylight.

Sør-Varanger was liberated by Russian troops in 1944 and was the first part of Norway to regain its freedom after four years of German occupation. The reconstruction of Finnmark started in 1945, but it still took 14 years before Kirkenes again had a church of its own. In the meantime services were held in barracks and other temporary religious meetinghouses. The vicars were provided with "church boats" to reach the most remote communities.