Work on Delft's second parish church started in 1381, when a temporary wooden church was built. Around this, a stone church was built starting from 1384, beginning with the transept and the choir. This part of the work was completed in ca. 1390. The west wall of the transept is bent, probably because the workers had to build around the altars of the wooden church, which were not to be moved. It seems that choir and transept were intended to have stone vaults., but sagging of the church probably was the reason why these was never added.

In 1390 work on the tower began, which continued until 1412, when the square lower part was completed. The nowadays empty niches originally had natural stone traceries.
After work on the tower had stopped the construction of the nave began, which lasted until 1435. Today the side-aisles each are a single space, but originally each trave was a seperate chapel. This was changed after the great fire of 1536. Traces of the old situation are still visible inside the church. Also, each trave originally had a roof of its own, instead of the single roof that now covers each side-aisle.
In 1432 work on the tower continued with the construction of the lower half of the first octagonal segment. Instead of brick on the outside this was covered with white Lede-stone. In 1441 the turrets at the corners of the square lower segment were added. In 1447 work on the tower again was stopped.

Work on a new choir started in 1453, beginning with a new ambulatory. The old choir was replaced starting from 1461, and the new one was finally completed in 1476. The choir is notably taller than the nave and is a rare example of classic Gothic in the Netherlands, having been built under the leadership of Jacob van der Burch, who was also responsible for much of Utrecht Cathedral. Like the Oude Kerk, the choir is supported by buttresses with arches in them.
The southern aisle was extended with three traves along the tower in ca. 1485 and completed with a baptistry. In 1510 the northern transept-arm was lengthened with a chapel dedicated to Mary. In 1494 work on the tower again continued, with the construction of a second octagonal segment, this time made of yellow Bentheimer sandstone, although this has weathered through the centuries and now has a blackish tint in some places. This stone had been delivered already in 1486, but out of fear that the tower might collapse under the weight of the stone it was not used for eight years, until it was finally decided to give it a try. The second octagonal segment was finished in 1495, followed by an apple-shaped spire a year later. This spire was lost in the fire of 1536, and replaced by another one, which itself burnt down in 1872. The current spire dates from 1875 and was designed by P.J.H. Cuypers.

On May the third of 1536 a flash of lightning hit the tower, resulting in a fire that not only severely damaged the two big churches, but also destroyed most of the town. Rebuilding the church was quickly started, but in a rather provisional manner. The natural stone traceries were renewed in brick. The usable surviving bits were used for balustrades. Pillars were repaired in such a primitive way that its a miracle the church never collapsed. During a restoration from 1923 until 1939 these were replaced. Also three new heavy buttresses were added to the leaning wall of the southern transept arm.

Initially the church was consecrated St. Mary, and since 1404 St. Ursula. With the iconoclastic riots of 1566 all building activities ended. Shortly after that the catholic history of the church ended as well, as early in the 80-years War the protestants confiscated the church and removed most of the catholic furnishing and simply renamed the church New Church. The choir has since become the mausoleum of the Orange family. The first Orange buried here was Prince Willem I, who initiated the war against Spain. His tomb was designed by Hendrick de Keyser.