The brick chancel and the nave both have round arch friezes below the cornice. The south door, partly bricked up, is still in use but the north door, whose remnants were uncovered in 1984, is completely closed. The nave was extended at the end of the 15th century when cross-vaulting replaced the flat ceiling. The remains of the priest's door can be seen on the south wall of the chancel. The east gable contains a rounded Romanesque window while traces of the other Romanesque windows can be seen in the masonry. The tower with stepped gables, built in the Gothic period, fills the full width of the nave. The porch dates from the same period. On the nave's eastern gable there is a relief of two heads and on the chancel's east gable, there is a head above the window. These have given rise to a legend about three virgins who had been to church in Horbelev and were murdered when returning home: one in Horbelev, one in Aastrup and the third in Grønsund. The three murderers were the women's brothers who were taken by robbers when they were small children. According to the legend, the three heads in Aastrup are those of the virgins while those on the tower at Horbelev are those of the robbers.
Interior
The Neoclassical altarpiece from 1838 has a painting of Christ at Emmaus by Fritz Westphal. The pulpit carved in the auricular style by Jørgen Ringnis is similar to those in Toreby and Væggerløse. The high crucifix from around 1400 used to hang above the chancel arch but is now above the door to the porch. It depicts a thin figure whose thorn-covered head falls to his right shoulder. The arms are long and thin and the hands unnaturally small and stumpy. The church's limestone font is Late Gothic.
Frescos
The frescos in the chancel and the nave from the late 15th century are probably the work of the Elmelunde Master and his workshop although they also appear to have been influenced by the nearby Brarup workshop. Rediscovered under the whitewash in 1901, they cover the Creation and the Passion. There are scenes depicting Christ bearing his cross, the suicide of Judas and the rich man and the poor man. In 1943, even older frescos depicting a Majestas Domini were discovered on the wall above the chancel arch.
