The earliest existing historical records of the church date back to the year 1327, but the church was not built that year. The first church was a wooden stave church that was likely built during the 13th century. This church was located about 380 metres (1,250 ft) to the northeast of the present church site at Ule (so that church was sometimes known as the Ule Stave Church). Very little is known about the old church. Sometime before 1683, the old church was closed. The old church stood for a long time afterwards, falling into disrepair. For a while, there was no church in Bagn and parishioners had to travel to the Reinli Stave Church.[3][4]
After about 50 years or so of no church in Bagn, the old Reinli Stave Church was also in poor condition, so the parish made plans to tear down that church as well and to build a new church in Bagn to serve both Bagn and Reinli. Permission was granted for this plan, but there was significant local opposition and protests, so the plan was cancelled. The parish then decided to build a new Bagn church and keep the old Reinli church too. Svend Tråseth was hired to design and build the new Bagn Church on a site about 380 metres (1,250 ft) southwest of the medieval church site. It was a cruciform design with a choir in the eastern wing. Local tradition states that some of the materials from the old stave church were salvaged from the old, unused, decaying building and used in the construction of the new church. Bagn Church was built in 1735-1736 and it was consecrated on 1 November 1736.[5][6][7]
In 1814, this church served as an election church (Norwegian: valgkirke).[8][9] 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.[8][10]
The church has undergone several extensive renovations and repairs. In 1833, extensive work was done on choir. In 1840, a sacristy extension was built to the east of the choir. In 1897, the structure was extensively rebuilt which included adding interior and exterior siding to cover the log building structure. New, larger windows were added and much of the interior was renewed and painted in new colors.[5][6]