By the end of the 14th century the population of Amsterdam had increased so much that one church wasn't enough, despite the recent enlargement of the Old Church. In 1408 the bishop of Utrecht granted official permission to build a second parish church. However, work on this New Church had already started in the 1380's and it could be consecrated soon after the bishop's permission was granted. The church was named Onze Lieve Vrouwekerk ('Church of Our Lady') but is now known as New Church.This is a tall building in a much more classic Gothic style than the Old Church. The first parts that were built are probably the choir and its side-aisles and the transept. Several enlargements and rebuilts have changed the look of the building since, while several buildings were built against it. In ca. 1435 the construction of the nave was started. In the late 15th century several chapels were added, followed by the addition of the clerestorey. After a fire in 1452 the choir was rebuilt with a clerestorey. In 1510 five radiating chapels were added to the choir. The southern transept-arm was enlarged, also after the fire of 1452. the northern transept-arm was built between 1530 and 1540 and features early-Renaissance influences.
The church never had a tower, although one was planned. In 1565 foundations for one had been laid, but the changed political ad religious climate prevented the further construction. In 1646, the church had become protestant by then, a new effort was made. Jacob van Campen had designed a new tower in a style that was still in a sort of Gothic style. In 1653 work on the unfinished tower ceased, and in 1783 it was demolished. Only the base at the western side of the church remains.
Between 1892 and 1914 the church was restored by architect C.P. Posthumus Meyjes, who added neo-Gothic elements, some of which were again removed during the restoration of 1955-1980.