The construction of the church began in the 12th century and ended no later than the 13th century. It appears in hewn stone blocks, which are characteristic of Vesthimmerland's Romanesque village churches. The tower and nave are built in brick. Extensions to the church date to the late Middle Ages. In the 18th century, the tower room was used as a burial chapel under the manor house Aggersborggård and delimited to the nave with a beautifully decorated iron lattice. The altarpiece is from the second half of the 16th century. It originates from Østerbølle Church, from where it was sold to Aggersborg Church in 1935.

During restoration work in the 1970s, several smaller runic inscriptions appeared, including the name Maria. Possibly the church was dedicated to the Virgin Mary. An exposed limestone-carving in the north wall translates to: "God... Thorlek from Hæra. Stand there! Peter S (val) e wrote me. Amen." The runes are dated to the period 1150-1536.