Den nuvarande kyrkan i Kirkenes blev färdig 1959. Kyrkan är ritad av arkitekten Sofus Hougen. Den gamla huvudkyrkan i Kirkenes förstördes i bombningar 1944. Tornet i den gamla kyrkan räddades och är en del av den nya kyrkan. Altartavlan är skapad av Kristoffer Leirdal. Altartavlan består av skulpterade människofigurer som tillsammans bildar ett kors.