The stone church was built around the year 1130. 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 130 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 site, just west of the old church. The new Gildeskål Church was completed in 1881 and it seated about 750 people.