The Valkhofpark ('Falcon's Court Park') is located on the site where until 1798 a castle stood, built by Charlemagne in ca. 777, destroyed by Vikings and rebuilt by emperor Frederick Barbarossa in 1155. After the French had destroyed much of the castle in 1795, and because the city needed the money, the ruins of the castle were sold that year and demolished for the stones. Only the St. Nicolaas chapel and the remnants of the nearby St. Maarten's chapel were excluded from demolition, as both were believed to have been built by the Batavians before the rule of the Romans and as such were a matter of local prestige.

In popular culture the building has been referred to as 'pagan chapel'  and 'Carlovingian chapel' until well into the 20th century, evidence that its earliest history is a bit of a mystery. The St. Nicolaaskapel was in fact originally a smaller copy of the chapel of Charlemagne's palace in Aachen, reason why for a long time it was thought to be from the late 8th century. Adding to the confusion was the use of parts of former Roman buildings and constructions, including a grave stone (nowadays in a museum) and numerous bricks and roof tiles. It is now believed the chapel was built in the 11th century, either in ca. 1030 or ca. 1047. That still makes it one of the oldest buildings in the Netherlands. It's also the only surviving Romanesque centralizing structure in the Netherlands; a similar building, but larger, was the St. Walburg church in Groningen which was demolished in 1627. The St. Nicolaas chapel faired better, but was used for storage after the Reformation and fell into decay. After the castle was demolished the chapel, like the nearby ruins of the St. Maarten's chapel, became an ornament in a newly designed park, serving no other function whatsoever.  

The chapel has an octagonal core with a 16-sided aisle of two storeys around it. Perhaps parts of Charlemagne's chapel were incorporated; the portal especially shows elements of Carlovingian architecture and is possibly the oldest part of the building. In ca. 1400 part of the outside walls were replaced with new ones made of brick, with ornaments and windows in Gothic style; these parts were covered with Gothic vaults. The octagonal central tower was added in the same period. A three-sided Gothic altar niche was reconstructed as part of a restoration in 1953-1958.