The combination of a facade in Renaissance style, a Romanesque nave and transept and a Gothic choir immediately makes it clear that this church has a long history. The St. John's church was built as the northern end of a cross of churches of which the first cathedral was the center, and must originally have been virtually identical to the Pieterskerk ("St. Peter's church") at the east end of the cross. Like that church, construction of St. John's was started shortly after 1040. Originally the church had a westwork consisting of a choir and two towers, one of which collapsed in the 14th century, while the other was demolished in 1682. At the beginning of the 16th century the choir was replaced by a new Gothic one. In 1580 the church was closed for services and was given a new function as a library. In 1656 the building became a reformed church, although the library remained in the church until 1821. After a tornado had seriously damaged much of the western side of the church in 1674, the last remaining tower was demolished and a new facade in Renaissance style was built in 1682, designed by Gijsbert Theunisz. van Vianen.
The wall of the southern side-aisle was partly renewed in brick early in the 17th century, and has two pointed windows. The Romanesque nave and transept were constructed out of tuff, although the top of the southern transept-arm's gable was renewed in brick as well after a fire in 1279. At the north side this top is missing.
A small belltower was added to the top of the choir in 1681, to compensate the loss of the two towers. The current one is is a copy from 1976.
Unlike St. Peter's church, the original red sandstone pillars of this church were encased in the current square pillars in the middle ages. Only a few of the current pillars are originals. In 1657 half of them were removed. The old situation was restored in 1977-1981. The nave has a painted wooden barrel vault which in parts dates from the 13th century. The painting was an attempt at simulating groined vaults.