The earliest existing historical records of the church date back to 1599, but it was likely built in 1580. Originally, it was called Vågsøy Chapel (Vågsøy kapell). The island of Vågsøy was historically part of the prestegjeld (parish) of Selje. In 1580, a small chapel was built on the island of Vågsøy, just south of Raudeberg on the Kapelneset peninsula, along the eastern shore of the island, about 2 kilometres (1.2 mi) south of the present site of the church. The chapel was served by the priest from Selje Church approximately once each month. The chapel was a small wooden building in a long church design. The nave measured about 10 by 7.5 metres (33 ft × 25 ft) and it had a choir on the east end of the nave that measured about 5 by 5 metres (16 ft × 16 ft). The main doors to the church were on far west end of the north side of the church. The church initially had a sod roof. In 1643, the county governor, Collett, described it as "Vaagsø Capell ligner en almindelig stygg lade." ("Vaagsø Chapel looks like an ordinary ugly barn.").[3][4][5]
In 1847, the local parish priest, Koren, proposed a new church at Raudeberg. The last worship service in the chapel was on 16 May 1853. After this, the building was sold to the merchant Ole Smidt from Måløy. In 1854, a larger church was built in the village of Raudeberg, about 2 kilometres (1.2 mi) to the north using plans by the architect Hans Linstow. The new church was called Vågsøy Church (Vågsøy kirke) until 1907 when a new church was built in Måløy. This church was then renamed Nord-Vågsøy (North-Vågsøy) and the other church was named Sør-Vågsøy (South-Vågsøy) church. The new church was in use until it burned down in 1945 during World War II. After the war, there was much to rebuild all over Norway, and so this church was not rebuilt until 1960. The new church was consecrated on 24 October 1960 by the BishopRagnvald Indrebø. The new church is constructed out of concrete. It sits on the side of a hill, so it has a partial basement underneath which includes utility rooms, a kitchen, meeting rooms, bathrooms, and storage. The church cost 750,000 kr to construct.[6][7][5]