The church of Koudekerke was preceded by several churches, the first of which according to some might have been founded by the missionary Willibrord in c. 690. There is no evidence for this, and the first known church is dated c. 1150. This was a small wooden church which in the 14th and 15th century was replaced by a bigger Gothic church. Little is known about this church, but a fragment of a painting from c. 1550 shows it with a relatively low nave, a higher choir and a big tower wth a tall spire.
The church was damaged during the fightings connected with the siege of Middelburg in 1572. The choir was demolished and the rest of the church was repaired to become a protestant church. In 1612 the church was in a bad state and had become too small. Two years later the building underwent the first of a series of renovations which were completed by 1650 and which left to nothing of the old church standing.
Not unusual for this period, the church was rebuilt in a style that still rooted in Gothic, with pointed windows and stepped buttresses. The parts above the walls were quite different however, with its tall hip roof and its open wooden tower at its center. A drawing from c. 1790 shows a small vestry at the eastern side which in 1827 was enlarged. In 1836 the church itself was renovated once more and the vestry rebuilt into a small 'palace' in early Neo-Gothic style. The church was probably plastered. Pictures made after 1900 show the walls covered with creepers which were removed during a restoration in 1962-1964, and so was the plaster. Plans were made in 2008 to replace the Neo-Gothic vestry by a moderrn building but thankfully the execution of this plan was prevented by heritage protection organizations.