It is known that many of the first churches were built on the sites of old pagan temples. In Elst a particularly large temple had been built in ca. 70, after a previous one was destroyed during the Batavian Rebellion in the year 69. This temple was used until the third century, after which it fell into decay.
A church was built in the 8th century by Werenfried, a follower of Willibrord, the first bishop of Utrecht. This was a small Romanesque church and consisted of a simple rectangular nave with a rectangular choir. It was built on the foundations of the second Roman temple, probably using the stones of the ruins. The church was enlarged several times, following the acquisition of relics of the founde and the pilgrimages in which this resulted. In the 15th century the church was replaced by the current Gothic building. In ca. 1450 the new choir was built, with the nave and the tower following between 1455 and 1484. Only a small part of the Romanesque church was retained and can be found at the northside, next to the choir. The church has a two-aisled nave, which is not unusual for a church in Lower Rhine Gothic (see Gothicism). The tower is related to the Utrecht-group of towers, consisting of two square segments decorated with series of three niches, and an octagonal upper segment.
After the church has been heavily damaged in 1944, a big restoration and partly reconstruction was carried out from 1949 until 1953. During this restoration the foundations of all predecessors were discovered. Today parts of these are visible in the yard around the church.