The earliest existing historical records of the church date back to 1432, but it was not new that year. The first church in Voll was likely a stave church that was built in the 14th century. In 1673-1674 the old church was torn down and a new timber-framed, cruciform church was constructed on the same site. The east–west wings measured to be 15.6-metre (51 ft) long and the north–south wings had the same length. There was a sacristy on the end of the east wing and a church porch on the end of the west wing.[3][4][5]
In 1814, this church served as an election church (Norwegian: valgkirke).[6][7] Together with more than 300 other parish churches across Norway, it was a polling station for elections to the 1814 Norwegian Constituent Assembly which wrote the Constitution of Norway. This was Norway's first national elections. Each church parish was a constituency that elected people called "electors" who later met together in each county to elect the representatives for the assembly that was to meet in Eidsvoll later that year.[6][8]
In the spring of 1895, the old church was torn down. Construction of a new church on the same site began right away and in 1896 the church was completed. The new church has a rectangular nave with a choir that has a nearly semi-circular apse on the eastern end. There were two sacristies on either side of the choir. There is a large steeple on the western end of the building above the church porch. The church was restored and renovated in 1964.[3][5]