In 1281 Valkenburg was nothing more than a group of houses grouped around the Heunsberg, a hill on top of which stood the mighty castle of which today only ruins are left. Yet in that year Valkenburg became a seperate parish. First services were held in the chapel of the castle, but work on a church started the same year. Until ca. 1600 this church was consecrated to St. Nicolaas alone, later St. Barbara was added. In 1633, after the protestants occupied the town, the catholics of Valkenburg were forced to share their church with the protestants. Although the latter were only a small minority they were powerfull enough to forbid the catholics to use an organ. The coming of the French in 1794 did not bring religious freedom, and until 1808 the protestants continued to use the church. In 1819 the church was finally fully returned to the catholics.
Of the original 14th-century church very little remains today. Only the tower and part of the nave are really old. And even the tower could have been demolished if Valkenburg's town-counsil had its way in 1846, when it preferred to replace the tower by a new one.
When the church returned fully in catholic hands in 1819 it obviously was much too small. In 1833 the nave had been extended while a new choir was added in 1836. C. Weber made a plan for a second enlargement in neo-Gothic style in 1875, but that plan was not executed. In 1891 a new portal was added to the front of the church, designed by P.J.H. Cuypers who also drastically extended the building in 1904. At the front a new porch with chapels on both sides was added. A three-aisled trave was built at the back of the transept, and behind that a new choir. The result is probably one of Cuypers' least successful designs ever.