Nøstvik Church is the oldest wooden church in Northern Norway (it is also called both Naustvik Church and Velfjord Church). Built in 1674 it replaced a small stave church, which had been built before the reformation of the Danish Norwegian church in 1536. Nøstvik Church is situated close to a beach by Sørfjorden, an obvious location in the days when boats were the main means of transportation.

The church has a log construction with vertical board on board external cladding. It has steep slate roofs and a turret with a tall spire close to the west sea-facing gable. Its footprint is cruciform and the transepts are narrower and thus have lower roofs than the nave. The chancel is narrower than the nave and its floor is one step up. A sacristy was added to the east end during the 1880s and again this is narrower with a lower roof ridge. The main entrance is through the north transept.