The small town of Heukelum emerged as an agricultural settlement in the early Middle Ages. Despite its status as a town, including several privileges, and the presence of two nearby castles, its sparsely inhabited surroundings limited its growth, and the town had still a largely agricultural character until part of the 20th century.

Heukelum has had a church at least since the year 996. It's not known what it looked like or where it stood. No traces earlier than the 13th century have been found; part of the apse and the north wall are the visible remains of that 13th-century church. The floor of that church has been found some 2 meters underground. In the mid-14th century a flood damaged the church and afterwards a new floor was laid at a higher level and the walls were heightened. Shortly thereafter the aisleless nave was extended with a side-aisle on the south side. At the end of the 14th century a sacristy was built at the north side. In ca. 1400 the old straight choir was replaced by the current Gothic choir. The floor was raised another meter. Plans to transform the church into a three-aisled church were made but never completed, as work at the northern side-aisle never started. At the south side the side-aisle was heightened by adding gables in the first quarter of the 16th century, making space for taller windows.

The church had a 60-meters tall tower. On the 5th of March 1699 it was struck by lighting and destroyed by fire, together with the south-western part of the nave. While the tower was repaired, the nave was demolished, leaving the eastern part of the church, being the choir, the easternmost part of the side-aisle and the sacristy standing at a distance from the tower. In 1728 a new polygonal, choir-like nave was built in the place of the old one. In 1772 the tower once again caught fire and was rebuilt to a lower height. In 1799 it became property of the local authorities, who had it demolished in 1829. In 1859 a small tower was added to the roof of the nave.

Between 1963 and 1966 the church was restored.