L'église (1701-1720), assez grandiose, occupe un bastion d'angle qui domine les résidences de la cité, bien en vue. Elle remplace un sanctuaire antérieur, supprimé pour dégager certaines directions de tir. Vauban réserva l'emplacement de la nouvelle église sur la place du Temple (emplacement d'un quartier occupé par les Templiers au XI et XII) et en donna les plans, mais l'ingénieur Robelin, muté en Alsace, partit avec les dossiers. La construction ne suit donc qu'approximativement le projet initial. Placée sous le vocable de Ste Marie et St Nicolas, patron des marchands.

De la précédente église, on n'a conservé que les deux lions couchés près du portail de la Collégiale. Vauban, à la demande de Louis XIV, accepta de superviser la reconstruction d'un édifice. Les travaux débute en 1703 et se termine en 1718 pous être consacré en 1726. Elle revêt le titre de Collégiale en 1746. Cet ensemble architectural occupe un flan Nord-Ouest de la ville fortifiée tout près des remparts.

Remarquable par sa façade imposante composée d'un portail encadré de niches abritant jadis les statues de St Pierre et St Paul. Porte en bois sculptée offerte par Louis XIV.

Deux clochers carrés, avec baies géminées et balustres, sont surmontés de dômes terminés par des lanternons. La tour de gauche porte un cadran solaire alors que l'autre possède une horloge. Vaste nef coupée d'un transept avec une abside semi-circulaire.

L'intérieur monumental reste classique avec des piliers décorés en trompe l'oeil (faux marbre). Stalles de bois dans le choeur accueillait autrefois les chanoines de la collégiale. Cette église dédiée à Notre-Dame et saint Nicolas a conservé un beau mobilier (autels, retables). Quelques tableaux d'un peintre guillestrois, Louis Court ornent le choeur et les bas-côtés (certains proviennent de la vaste chapelle du fort des Têtes, transformée en caserne au XIX). Divers autels (autel de la Vierge, du St Esprit, de St Joseph) réalisés en bois sculpté et doré. Buffet d'orgue du XVIII.