After the old church of St. Nicolaas had been taken from the catholics by the protestants in 1577, it would take until 1635 before the catholics had a church of their own again, a hidden church which remained in use until 1780. That year it was replaced by a new one, which in many ways was still a hidden church. Within less than two decades later the catholics were granted more religious freedom, and they could have built a real church. However, it lasted for more than a century before they did. In 1887 the catholics of Ijsselstein finally had a church the size of which could compete with the old St. Nicolaas and perhaps was even more impressive.

This 'new' St. Nicolaas is one of architect Alfred Tepe's most important works. It's a three-aisled hall-church in a neo-Gothic style that, as with all of Tepe's churches, was to a high extent based on Lower Rhine and Westphalian Gothic. For his design for the St. Nicolaas he combined a Westphalian type of hall-church, with side-aisles lower and narrower than the nave, with a Lower Rhine-inspired architecture. On the western side, flanking the tower, the side-aisles extend to become chapels. On the eastern side they are polygonally closed. The side-aisles have shed roofs for every trave. More than is the case with most of Tepe's churches, the exterior is ornamented with balustrades and stepped buttresses with pinacles while the tower has a large number of niches with traceries. The interior, with works by other members of the St. Bernulphus' Guild, is still largely intact. In 1972 the church was granted the title Basilica Minor.

In 1891-1892 Tepe built a very similar, but smaller and slightly simpler, church in Raalte (Ov).