In 1433 it is mentioned as Vor Frue Kirke (Church of Our Lady), as written on the altar chalice.

In the period between 1661 and 1675 the Danish crown sold the church to the Count Mogens Friis who made it a part of the duchy Frijsenborg.

[3][4] Kolt Church consists of Romanesque apse, chancel and nave with two late-Medieval additions: the porch in the south and the tower in the west.

The Romanesque sections are built of rough and hewn granite boulders on a chamfered base; ashlar were used in the corners and around the windows and doors.

In the masonry of the tower a quantity of re-used granite ashlar is included which may have been brought here from a demolished church.