Dating from the second half of the 12th century, the church has a Romanesque chancel and nave, a large burial chapel from 1636 and a tower from 1877.

In 1177, the Crown's clerical appointment rights were transferred by King Valdemar to Ringsted Abbey, which continued to have responsibility over Halsted Priory.

At the time of the Reformation, ownership returned to the Crown, which retained it until 1719 when Halsted Priory was transferred to Jens Juel-Vind in exchange for Juellinge on Zealand.

When it became the priory church at the end of the 13th century, the chancel was extended to the east, its three-sided gable replacing the former apse.

The auricular pulpit (1636), displaying representations of Faith, Hope and Charity as well as the arms of Prince Christian and Princess Magdalene Sibylle, is the work of Jørgen Ringnis.