The church of Oost-Souburg was founded in the first half of the 13th century as a daughter church of West-Souburg. Possibly the church was preceded by a chapel.
The church was completed is unknown around 1250, the year it was consecrated. At that time the church was a three-aisled pseudo-basilica with a short tower and a narrower five-sided choir and was probably in Schelde Gothic-style.
In 1566 the church was plundered and damaged by protestant extremists. During the war that followed, the Eighty Years War, the church was reduced to its outer walls and the tower.Between 1578 and 1603 the building was restored, now to serve as a protestant church. In this period the tower was heightened and, probably, the choir demolished. At the west side of the southern aisle a narrow and tall pointed window was added and closed again, followed by the addition of a circular window next to it, cut right through one of the buttresses of the tower. At the north side a similar window was added.
At the end of the Second World War the church was damaged by a flood which lasted from January 1945 until March 1946. From 1947 until 1950 it was restored. In 1987 a community building was added to the east side, followed in 2007 by a meeting room made out of glass on the north side of the nave.