The earliest existing historical records of the church date back to the year 1589, but the church was not new that year. The first church in Kleive was a stave church that was located a little to the southwest of the present-day building. The first church may have been constructed in the 14th century. The medieval church was repaired and renovated many times over the centuries, the final time was in 1682, but by then the church was in very poor condition that it was in danger of collapsing. In 1697, the old church was torn down and a new church was constructed to replace it. The new building was a wooden, cruciform building.[3][4]
In 1814, this church served as an election church (Norwegian: valgkirke).[5][6] 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.[5][7]
In 1857, that cruciform church was torn down because it was getting too small for the parish. A new church was constructed in 1857-1858 by an unknown architect, although there is some evidence that it could have been Christian H. Grosch.[4] The church was built in an Empire style with an octagonal design. There is a rectangular church porch on the west end of the octagonal nave and a choir and sacristy on the east end of the building. There is a tower on the roof above the centre of the octagonal nave. The new building was consecrated on 20 August 1858.[4]
