The majority of Norwegian churches built from 1800 to the beginning of the 20th century were made of wood. In accordance with Norwegian tradition, they were often made of timber, using the cogging joint method and typically clad with exterior weatherboarding. This was also the case with the Valberg Church. The long façade has a symmetric design and four tall windows on the mid-section. Tall pointed arch windows were often employed in Neo-Gothic churches. Another characteristic trait was the division of the wall plane, via pilasters that stand between each window. It was necessary to reinforce/buttress the long walls with supportive beams. These were usually pronounced on the exterior, often in the form of a pilaster.

The first church in Valberg was built around 1660, but was destroyed by a storm in 1749. Roughly three years later, a new church was built, but in 1818 it was also devastated by a storm. A new church was built the following year, but was dismantled one year after today's church was completed. Today's church (the fourth one in the series) was built in 1888-89 by A. Grenstad. The cost of construction was 16,700 Norwegian crowns. In 1951, during restoration work performed on the Valberg Church, a concealed letter was found underneath the floor of the pulpit. The letter read "This church is built by the undersigned A. Grenstad from Vefsen Mosjøen in the year 1888 where it was then completed. Two of his sons assisted with the work. It is the 8th church that I have built, not including seven other churches I have restored. In total I have built 15 churches to this date. I will turn 67 years old this month. A. Grenstad was born in Kløbo on the farm Grenstad."