The church of Nijswiller originally was very similar to other churches in this region, a simple one-aisled church, consistent of little more than a rectangular nave with a rectangular choir and a small, mostly wooden tower. Much like the old church of nearby Lemiers, in fact. There have been rumours that the church has its origins in either a hunting cabine or a chapel belonging to Charlemagne, but the oldest surviving parts of the church are fragments of a limestone wall from the 12th century that can be seen at the north side of the nave. The general layout of the building probably changed little or nothing over the centuries. A new rectangular choir was added in the 17th century, and although the church was never of great importance, always falling under the supervision of another church, it seems likely that this was a replacement of an older choir.
At the end of the 19th century the church had become too small. In 1890 P.J.H. Cuypers made a plan to enlarge the building. The choir was demolished in 1895 and a revised plan for an extension was executed by Cuypers and his son Jos the same year. A three-aisled extension was added to the nave, illuminated by a 'clerestorey' with only one circular window on each side. To the east of that a new neo-Romanesque choir and a sacristy were built. To the old part of the nave a porch was added while the walls were heightened a bit. For all of the work natural stone was used to match the old building. Oddly, many sources state 1905 instead of 1895 as the year of enlargement.