On raconte que de jeunes pâtres découvrirent, un jour, une image de la Vierge, près d'un saule. Ils la rapportèrent en lieu sacré mais, chose étonnante, la nuit suivante, l'image rejoignit son arbre...
Une chapelle fut alors construite en cet endroit et dédiée à la Vierge noire, patronne de la ville depuis le 13e siècle.

C'est à l'emplacement de celle-ci que l’église Notre-Dame est édifiée de 1505 à 1695, à l'instigation de Marguerite d'Autriche.

Œuvre de l'architecte Guillaume Perrin, aidé de Loys van Boghem qui réalisa l'église de Brou, ce monument historique mêle le style Renaissance, en son extérieur, et gothique flamboyant, en son intérieur. Le tableau miraculeux et la Vierge noire y sont toujours vénérés...

Décapité en 1794 par Albitte, le clocher est protégé d’une couverture provisoire pendant plus d’un siècle avant d’être reconstruit à l’identique par l’architecte Tony Ferret en 1911.

Le sculpteur Alphonse Muscat réalise quant à lui la décoration du cadran de l’horloge de la façade ouest en représentant un homme et une femme de part et d’autre, symboles de la naissance et de la mort mais aussi du temps qui passe. Appelée L’heure de la naissance et l’heure de la mort, l’œuvre deviendra pour tous, sans doute par pudeur, Le Jour et la Nuit.

En 1914, la collégiale est classée Monument historique.