Reine Church is a log church with external wooden cladding that now seats 250 people, and it has been through a process of many changes. The original building had a turret on the roof above the nave

external wooden stairs on the east side led to the main entrance and vestibule under the gallery and there was no sacristy. The turret had wooden shingles and the main roof had wooden board on board cladding treated with iron sulfate. Inside, under the gallery, there were originally a reading room for fishermen and at the front left of the nave there was another smaller gallery reserved for prominent congregants.

The tower was added in 1923 at the northern end of the building. It rests on a stone plinth and the spire was transferred from the old turret. It has an internal staircase that greatly improved the access and capacity of the gallery. In 1933 Moskenes Parochial Council decided to increase the seating capacity by removing the reading room walls under the gallery. A new entrance had already been established via the tower.

The sacristy was added in 1955 and at the same time water and toilet were installed. A major external renovation took place in 1966 with new windows and wooden cladding as well as repairs of the slate roof and the tower's copper cladding. The interior was not painted until 1969 and the gallery for prominent congregants was removed at the same time. Since then the interior has more or less remained as we see it today.