Dans sa séance du 16 février 1902, le conseil municipal de Saint-Martin-Labouval approuve le projet d’abandon de l’ancienne église au profit d’un nouvel édifice. L’église, d’origine médiévale, est en effet en mauvais état : le clocher et la toiture nécessitent des travaux à hauteur de 8000 francs, les voûtes sont lézardées et représentent un « danger permanent », sans compter le manque de lumière et l’insalubrité causée par sa situation, en contrebas du cimetière, la rendant « toujours humide » et où « tout s’y détériore rapidement ». Aussi, l’idée d’une nouvelle église est-elle accueillie favorablement par les habitants : preuve en est la souscription ouverte spontanément dans ce but et qui produit en quelques jours la somme remarquable de 36 300 francs ! La tradition orale veut que le baron Antoine de Vauzelles, propriétaire de l’usine de phosphates de Cénevières, a contribué à hauteur de 20 000 francs ce qui est tout à fait vraisemblable au vu de la somme récoltée. Le curé n’est pas en reste puisqu’il promet un don de 702,84 francs. Quant au terrain choisi pour implanter la nouvelle église, au centre du bourg, il est offert gracieusement par Marie Lucie Tardieu à la commune.

Les plans et devis en sont dressés par l’architecte départemental et diocésain, Emile Toulouse (Mende, 1860-Cahors, 1927), et approuvés par délibération municipale du 3 août 1902. Le coût des travaux est alors évalué à 49 302,84 francs. Un projet jugé bien trop onéreux par le Comité des inspecteurs généraux des édifices diocésains et paroissiaux dans sa séance du 14 février 1903. Celui-ci demande notamment de supprimer la coupole, un argument repris par le préfet qui, le 20 février 1904, enjoint le maire de renoncer à cette « disposition inutilement luxueuse ». Il n’en sera rien. Le projet suit son cours tel qu’initialement prévu mais la subvention accordée par l’Etat, soit 5000 francs, ne représente que la moitié du secours sollicité… Enfin, le 19 mars 1904 les travaux sont attribués à l’entrepreneur Jean-Pierre Flaujac pour un montant de 37 705,92 francs. Le 29 août la première pierre est posée et bénite solennellement par Mgr Enard, l’évêque de Cahors. Mais un an plus tard des travaux supplémentaires de 11 235,83 francs sont jugés nécessaires pour « la solidité de l’édifice », sans doute le rabais accordé par l’entrepreneur avait-il été trop important… Afin d’y faire face, la commune décide d’emprunter 2000 francs le 16 juillet 1905. Elle n’avait jusqu’alors pas eu besoin de participer financièrement au projet. Les travaux sont achevés en 1907 mais le décompte définitif fait apparaître un montant très largement supérieur aux prévisions : 56 119 francs ! Aussi, la commune décide-t-elle de souscrire à un nouvel emprunt de 4500 francs le 16 juin 1907 afin de solder les travaux. Une première partie des vitraux – ceux du chœur, commandés à la maison Lorin de Chartres, est d’ailleurs posée cette année-là. A noter également que le carrelage du chœur a été fourni par la manufacture Carrelage céramique de Paray-le-Monial.

Toutefois, le coût considérable du chantier provoque quelques modifications. Ainsi, le clocher ne reçoit pas son élévation prévue dans le plan initial. Il faut attendre vingt ans pour que ce projet soit relancé par le maire et le curé. L’architecte Georges Bergougnoux (Brive, 1891-Cahors, 1972) est alors chargé de son exécution. Le 12 juillet 1927, il dresse un devis de 50 015 francs (soit 10 000 francs or), en grande partie couvert par une souscription volontaire des habitants qui s’élève à 42 500 francs. Les travaux sont réalisés en 1929, ils consistent notamment au démontage du campanile octogonal qui avait été placé en 1907 et qui sera remonté une fois l’étage de la chambre des cloches construit, donnant ainsi à l’église son allure initialement imaginée par l’architecte Toulouse.