The church's name is first recorded in 1335 in a document attesting to its having been dedicated to the Virgin Mary. The building, made essentially of fieldstone but with some sandstone, consisted of a Romanesque chancel and a nave, a western tower, and a Gothic porch for the south door. There had once been an apse but by 1861 it had been replaced by a small extension to the chancel. The tower of the old church is said to have served as a landmark for sailors. The old building was torn down in the 1880s in connection with the construction of the new church.
Today's building
The new church was consecrated on 19 July 1885. It lies on high ground in the southern part of Vestermarie parish, the largest in area on the island of Bornholm. It was designed in the Neo-Romanesquestyle by Mathias Bidstrup and consists of a chancel with an apse, a nave and a tower, all of reddish granite with corners and trimmings of grey stone. The main entrance is on the western front of the tower. The roof and the pyramid spire are of slate.