Helsingør developed rapidly after Eric of Pomerania introduced customs fees in the 1420s for ships sailing through the Øresund, soon becoming one of Denmark's largest market towns.

The church is mentioned in several late 15th-century documents in connection with Johan Oxe's Chapel and, later, the inscription on the alarm bell in 1511.

After the Reformation, Saint Olaf's gained a reputation as a Catholic stronghold, a Protestant priest saying in 1536 he was unable to take up his appointment there.

In the early 15th century, the church was extended westwards in the Gothic style, including a tower at the west end with stepped gables.

In addition to the tower at the west end, there is a porch on the south side of the building while the Trinity Chapel and the sacristy extend towards the north.

The church is exceptionally well decorated with two small Dutch alabaster altarpieces donated by Birgitte Gøye and Herluf Trolle (on either side of the main altar), a carved pulpit created by Jaspar Matiessen in 1567 with a canopy from 1624, and a Baroque altarpiece (c. 1664) designed by Lorentz Jørgensen in the auricular style.

[4] There are also a number of frescoes in the church, notably the decorative painting with flowers and leaves on the nave's fourth vault, dated to the mid-16th century.