The Grote Kerk ('Great Church'), or St. Bavo as it was originally named, gradually replaced an older church on the same location. The current church is one of a series of churches in the area of the coast of Holland that were built in the Brabantine Gothic style, adapted to local circumstances, the so-called Kustgotiek ("Coast Gothic", see the page about Gothic).

As usual, the first part that was constructed was the choir. This was built from 1370 until 1400 by architect Engelbrecht van Nijvel. It was mostly executed in brick, with only a limited use of sandstone. The choir has a heavy, closed look with relatively small windows. It's also remarkably deep for what was intended as a parish-church, and the reason for its size is still a mystery.

The transept was built from 1445 to 1455 under architect Everaert Spoorwater in Brabantine Gothic style. Originally the transept was lower than it is today; between 1480 and 1495 it was heightened with a section that is still easy to tell apart from the older parts. In 1892 the transept was vaulted at the original intended height, making the space above it useless. Spoorwater was also responsible for the nave, which was built in two parts. From 1456 to 1470 the outer walls of the side-aisles and the lower part of the western facade were built around the old church and tower, which were demolished in 1471. The nave was finished in 1478, again in Brabantine Gothic style but with wooden vaults.

In 1502 work began on the construction of a crossing-tower out of stone, but since it turned out to be far too heavy it was again demolished in 1517. Instead a wooden steeple was built on the crossing, covered with lead.

Although the church was originally built as a parish-church, it became the cathedral of the newly formed diocese of Haarlem in 1559. It was the only church in the city that was fit for this function, but the deep choir was especially convenient. The St. Bavo remained a cathedral for 19 years only, although it is still often referred to as such. Already in 1566 the first attacks on this symbol of Roman-Catholicism were carried out. Since the iconoclastic riots of that year of the original typically Catholic decorations only the statue of St. Bavo at the front remains. Legend has it that protestant vandals managed to destroy all other statues of the church, but that two of them died during their attempts to destroy St. Bavo's statue as well, so they finally left it alone. This incident however did not stop them from confiscating the church in 1578. The St. Bavo has been a protestant church ever since.