In the early 9th century the missionary Ludger founded a chapel in Zelhem, possibly a converted pagan temple, and dedicated it to St. Lambertus. The foundations of this chapel were found during excavations in 1946. Little is known about its history but by the 11th century it, or a similar-sized successor, had become the choir of a fairly large church in Romanesque style. It is unknown whether this church was orginally an aisleless church to which later side-aisles were added, or if it was built as a three-aisled church right away. The church was built of tuff, and the only remaining part of it is the front of the tower which was added in the 12th century. It was rebuilt in 1662 using bricks and in 1845 it was heightened.

The current Gothic choir with lateral chapels was built in the mid-15th century, probably around the old choir. After that, the Romanesque church was replaced by the current pseudo-basilica in Gothic style. Although this part of the church was built of bricks, some parts of the walls were clad with tuff from the predecessor.

The church was set on fire in 1572, causing the tower and the vaults of the nave to collapse. By 1662 the church was probably rebuilt, now as a protestant church. In 1674 the tower once more collapsed, now due to a storm, causing serious damage again. It is unknown when the church was once again repaired, but a drawing from 1743 shows it very complete.

In ca. 1842 a small prison and a firehouse were built on the north and south side of the tower respectively. In 1843 the entrance in the tower was closed and replaced by by new ones in the north and south sides of the nave, as well as on the east side of the choir. In March 1945 the church was badly damaged by bombs. In 1946 archeological diggings revealed the foundations of the predecessors of the church. In 1949-1950 the church was restored; the former prison was removed, the entrances of 1843 were closed and the portal in the tower was reopened.