The earliest existing historical records of the church date back to the year 1327, but it was not new at that time. The first church building in Sande was likely a wooden stave church that was likely built during the 13th century. Around the year 1620, the medieval church was torn down and replaced with a new timber-framedlong church on the same site. The nave of the new church measured 10 by 9.5 metres (33 ft × 31 ft) and the chancel was about 5 by 6 metres (16 ft × 20 ft).[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 1861, there were two small landslides that came down off the mountain just north of the church. Both landslides were stopped by the rock walls on the border of the graveyard which surrounded the church, thus saving the church from damage. In 1864, the old church was torn down and replaced with a new church building on the same site. The new church was designed by Hans Linstow and it was built during 1864 and consecrated on 5 December 1864. The church nave measured 9.5 by 18 metres (31 ft × 59 ft), nearly double the length of the older church. Originally, the choir was in the same room as the nave, giving the church a rectangular design. In 1865 a new sacristy was built on the east end of the nave. In the 1943–1944, the church was significantly rebuilt using drawings by Johan Lindstrøm. The sacristy was converted into the choir and a new sacristy was constructed on the south side of the new choir, giving the church a long church design.[3][4][5]