The county governor's headquarters is situated south facing on the edge above the actual town centre, like a backdrop on top of the street Tollbudgata - with a neighbouring church and vicarage towards the east. When seen from the town centre, the gable ends of the complex's two rectangular blocks, one higher than the other, appears like a concrete sculpture towering towards the sky.

In 1888 it was decided that the county governor should have a permanent residence in Vadsø. The county governor's residence (1895) was build adjacent to the church (1861)

both structures towered above the town, on the crest of the hill. Both the county governor's residence and church were built of wooden materials, and both burned in the autumn of 1944. After they were destroyed, the county governor's administration building and residence, along with the church, were rebuilt on their original sites above the town centre - but with modern materials and a new architectural form of expression.