The church of Oldenzijl is a one-aisled building with a Romanesque semi-circular apse. The church dates from the first half of the 13th century and until the Reformation was called St. Nicolaas.
It is assumed that the eastern part of the church is older than the western part. The apse is purely Romanesque and is considered a highlight of this style in The Netherlands. The decorative details indicate an influence from the Rhineland. 
The nave features elements of Romanogothicism. Remarkable are the windows in the shape of a four-leaf clover in both the northern and southern walls of the straight part of the choir, basically the eastern-most trave of the nave. The one on the south side is a reconstruction, added during a restoration in the 1950's. The windows in the two eastern traves of the nave are decorated with little columns, which the two western traves lack, which is considered evidence for the theory that the eastern traves are older.
The small tower at the front of the roof dates from 1683. As common in this part of the country, the church used to have a free-standing tower. This tower was demolished in 1829.