The foundation of the church may be connected with the Christianization campaign of bishop Kunibert of Cologne in the seventh century.

The building was expanded several times in the thirteenth to sixteenth centuries, including an impressive ambulatory.

Pope Pius IV authorized the establishment of its own chapter, in 1475, making St. Stephen's independent of Cologne.

In 1591 Saint Stephen's was converted to a Protestant church after the city was captured from the Spanish (during which the steeple was severely damaged), which it has remained since except for a Catholic interlude around 1670.

In 2001 the church received two stained-glass windows of Marc Mulders entitled Pelican and Stigmata.