L'église est placée depuis le 16e siècle sous le vocable de Saint-Sulpice, évêque de Bourges du 7e siècle, elle était auparavant appelée Notre-Dame ou Notre-Dame de Saint-Sulpice (Laurens, p. 107-108). La ville de Saint-Sulpice est fondée au 13e siècle par Sicard Alaman sur le modèle des bastides. Traditionnellement, les bastides accueillent en son centre la place du marché or à Saint-Sulpice, l'église est élevée à cet emplacement (Laurens, p. 107). Une ancienne église était placée en dehors des fortifications sur le Plô de Fontpeyre, au sud de l'église actuelle (Cabié, p. 55). En pleine guerre de Cent Ans, la cité préfère établir une nouvelle église à l'abri des remparts. L'église dotée d'un clocher monumental avec tours et mâchicoulis devient l'ultime défense de la ville en cas d'incursion (Cabié, p. 55).
L'église est construite au gré des dons et legs des habitants durant deux siècles, du milieu du 14e au milieu du 16e siècle (Laurens, p. 138). Les dons et legs par testament permettent de retracer les différentes phases de construction car chaque financement est attribué à une réalisation particulière. Laurens mentionne précisément ces documents dans sa monographie de la ville de Saint-Sulpice publiée en 1893.£La construction de la nef débute dès le 3e quart du 14e siècle (dons de 1365 et 1367, Laurens, p. 138). Le chevet est commencé dès 1415 par un maçon toulousain Bernard du Solier puis est continué par Guillaume de Malhoc pour être achevé par le charpentier Candet (Laurens, p. 138).
Le clocher est construit indépendamment de la nef à la fin du 14e siècle à l'initiative de Gaston Fébus, seigneur de Saint-Sulpice mais son achèvement est interrompu à la mort de ce dernier. Le nouveau seigneur, le duc de Berry, modifie le projet du clocher ; il autorise la construction d'un clocher-arcade moins haut que celui projeté afin qu'il ne dépasse pas la hauteur du château de Saint-Sulpice (Laurens, p. 228). Cependant, le clocher est augmenté durant la première moitié du 15e siècle grâce aux nouveaux dons et legs des habitants (Laurens, p. 229) ; deux imposantes tours et trois flèches polygonales viennent s'ajouter à la façade. Le clocher arbore aujourd'hui deux styles différents car il a conservé ses arcades de la première construction de la fin du 14e siècle. Malheureusement, il est le seul vestige médiéval encore présent de l'église qui est rebâtie à la fin du 19e siècle.
En mars 1884, la commune lance des travaux de réparations et d'harmonisation des chapelles de l'église exécutés par l'entrepreneur Pierre Rouayse sous la direction de l'architecte toulousain Gabriel Bréfeil (A.D. Tarn : 2 O 271/2). La taille des chapelles est uniformisée et les murs en mauvais état sont reconstruits. Malheureusement, des problèmes structurels provoquent l'effondrement de la voûte de l'église le 6 juillet 1884. Les travaux de Bréfeil et Rouayse sont directement mis en cause dans la catastrophe (Mahoux, p. 202-203). Excepté le clocher qui est structurellement indépendant de la nef, l'église doit être entièrement reconstruite. Les travaux sont réalisés entre 1886 et 1888 par l'entrepreneur Ulysse Bertrand dirigé par l'architecte départemental Hess (A.D. Tarn : 2 O 271/2). La commune et la fabrique de la paroisse financent conjointement la reconstruction. Des emprunts et une imposition extraordinaire sont nécessaires mais insuffisants pour subvenir aux dépenses des travaux (A.D. Tarn : 2 O 271/2). Le plus beau trésor de l'église est alors cédé au musée de Cluny contre une subvention : un triptyque en ivoire daté du 14e siècle (Mahoux, p. 204 ; A.D. Tarn : 2 O 271/2). Le maître-autel et la chaire sont commandés aux ateliers Virebent de Launaguet (Mahoux, p. 205), l'église peut alors accueillir sa première messe dès le 1er avril 1888. Quelques années plus tard, la partie occidentale de l'église entre à son tour en travaux sous la direction l'architecte toulousain Joseph Thillet. La tribune et le portail d'entrée sont réalisés en 1894 par l'entrepreneur Marcelin Reilhes (A.D. Tarn : 2 O 271/2). Le grand orgue de la maison Théodore Puget est installé dès 1896 (Mahoux, p. 205). La même année, l'entrepreneur Emile Calvet commence la restauration du clocher. Il fait appel au sculpteur Dedieu pour la réalisation de sculpture en pierre de taille : la clef aux armes de Gaston Fébus pour le portail ainsi que huit corbeaux représentants des personnages de la Bible (A.D. Tarn : 2 O 271/2). L'architecte intervient également sur les flèches du clocher ; deux des trois flèches sont reconstruites, la flèche centrale est conservée mais ses mâchicoulis sont refaits (A.D. Tarn : 2 O 271/2). L'horloge placée sur la tour nord est remplacée en 1922 par un modèle provenant de la Maison Odobey Cadet (A.D. Tarn : 2 O 271/2).
Le choeur est éclairé par des vitraux installés en 1886-1886 par M. Châlons, peintre-verrier à Toulouse (A.D. Tarn : 2 O 271/2). Les archives ne mentionnent aucun autre peintre-verrier excepté Châlons, laissant supposer que ce dernier soit l'auteur de l'intégralité des vitraux de l'église. Le vitrail central du choeur porte les noms du curé Thiéry et du maire Picard ainsi que les armoiries de la ville, celles du pape Léon XIII et celles de l'archevêque d'Albi Jean-Emile Fonteneau. Ces noms et armoiries n'indiquent pas un financement personnel mais une liberté prise par le maire et le curé de l'époque. Cette liberté est vivement critiquée par la municipalité suivante (A.D. Tarn : 2 O 271/2). Le vitrail de la première chapelle sud est lui postérieur, il est signé A. Ouillac et daté de 1938.
Enfin, le choeur et les chapelles attenantes sont recouverts de peintures murales réalisées après la seconde guerre mondiale. Les peintures du choeur suivent un même programme iconographique représentant trois sacrements. Elles sont signées André Poudens et datées de 1947 et 1948. De gauche à droite figurent le Baptême peint en mai 1948, l'Eucharistie en 1947 et la Confirmation en février 1948. Les peintures de la chapelle de gauche sont peintes par M. André en 1949 et représentent la vie de Saint-Sulpice, patron de l'église. La seconde chapelle est dédiée à Sainte-Cécile, patronne du diocèse d'Albi, les peintures portent la signature de F. Soulier et la date de 7 novembre 1949. Deux autres noms figurent sur cette peinture (N. Crassous, R. Faure).
