The earliest existing historical records of the church date back to the year 1225 when it was mentioned in the book Hákonar saga Hákonarsonar. The first church in Stange was a stone building that was constructed during the 12th century. There is some evidence that a wooden post church was on the site during the 11th century. This is based on the fact that in 1986, an archaeologist found graves on the site that are older than the 12th century church. Around the middle of the 13th century, the old church was deemed to be too small for the parish, so a new church was to be built on the same site. Construction seems to have started with the choir, so that the interruption in church activities should be as short as possible, and the new church was built around the old one. The new church was a long church with a rectangular nave measuring about 21 by 15 metres (69 ft × 49 ft) and a smaller choir measuring about 11 by 9 metres (36 ft × 30 ft). A sacristy on the north side of the choir was built during the 14th century.[3][4]
On 17 July 1620, the church was struck by lightning and it burned the roof and most of the interior furnishings. Thus, the medieval interior was destroyed, and much of what we see today is a baroque interior from the 17th century and early 18th century. The church was rebuilt quickly after the fire and a small tower was built on the roof of the nave. In 1703, a large transept extension was added to the north of the nave so that the church has been given a kind of T-shape or a partial cruciform design. The new wing is referred as the New Church (Norwegian: Nykirken). In 1772, the tower was rebuilt with a much taller and larger tower. It is said to be Norway's tallest cantilevered wooden construction for that time period.[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]