The earliest existing historical records of the church date back to the year 1432, but the church was likely built around the year 1130,possibly by King Øystein. The medieval stone church originally had a rectangular nave and a narrower and almost square chancel with a lower roof line. At some point, the east and west gable walls were rebuilt as well as the south wall.[3]
Around the year 1710, the church had a large fire. Afterwards, the church was repaired and an addition was added to the south, making the church half-cruciform. All of the interior furniture and decor was destroyed in the fire as well. The pulpit was painted by Gottfried Ezekiel (ca. 1719-1798). He received a commission as a painter in Bergen during 1744 and starting in 1751 he arrived in northern Norway, where he painted a number of church altarpieces. Gottfried Ezekiel also painted the altarpiece that stands today in the new Gildeskål Church.[3][4]
In 1814, this church served as an election church (Norwegian: valgkirke).[5] 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 at Eidsvoll Manor later that year.[5][6]
In 1851, a new law was passed that said that all rural churches had to be able to fit at least 30% of the parish members in the church building. Since this church could only seat about 275 people, it was too small, therefore a new church had to be built for the parish. It was decided that the new church would be built on the same property, about 100 metres (330 ft) west of the old church. The new Gildeskål Church was completed in 1881 and it seated about 750 people. Since that time, the old church was closed and turned into a museum.[7][8]