Jusqu'à la Révolution Montredon était un prieuré dépendant de l'abbaye de la Chaise-Dieu et comprenait deux paroisses, Saint-Michel de Montredon et Sainte-Madeleine de Poustans son annexe (Clary).

Dès 1861, le conseil municipal, sur les recommandations de l'évêque, reconnaît que l'église a besoin de réparations. Mais son état nécessitant des travaux trop importants, et par ailleurs jugée insuffisante pour la population, il est finalement décidé de la reconstruire. Le projet est confié à Hippolyte Poujade (Rodez, 1827-Figeac, 1888), conducteur des Ponts et Chaussées, qui en dresse les plans et devis datés du 6 mars 1875.

Le 7 juillet, en réponse aux modifications demandées par le Conseil des Bâtiments civils du Lot - pour raisons d'économie, Poujade accepte de diminuer l'église d'une travée, de réduire la hauteur des bas-côtés, de la nef et du clocher, et de retirer les ornements qui n'étaient pas indispensables (les clochetons sur les contreforts notamment). Ce nouveau projet est approuvé par le préfet le 16 juin 1876. Le 9 juillet 1876, les travaux sont attribués aux frères François et Baptiste Lucien de Viviez pour la somme de 27 827,64 francs. Mais ce projet n'aurait pu voir le jour sans la détermination de l'abbé Desclaux (curé de 1873 à sa mort en 1885) ni la mobilisation exceptionnelle des paroissiens qui souscrivent à hauteur de 19 570 francs, sans compter les transports de matériaux qu'ils s'engagent à faire pour 3000 francs. De son côté l'Etat accorde un secours de 5000 francs. Le 9 août le piquetage est effectué et il est finalement décidé de revenir sur le projet initial qui offre une plus grande longueur. Par contre, la largeur du nouvel édifice est égale à l'ancienne et les murs latéraux de la nef sont conservés sur une hauteur de 1,50 mètres. Quant au choeur et au clocher ils sont détruits. Le devis stipule en outre que la pierre de taille provient des carrières de Montmurat (Aveyron).

Malgré les injonctions de l'architecte, les entrepreneurs vont accumuler retards et malfaçons. Ainsi, Poujade écrit-il le 23 décembre 1878 : « La maçonnerie de pierre de taille ressemble à une réparation faite après une dévastation, le ciment ressort partout ; les ravalements sont à faire ou à refaire ; les malfaçons, en certains endroits dangereuses, sont à réparer ; la toiture laisse passer l'eau partout et le choeur est encore couvert en chaume en partie ; les voûtes sont incomplètes, le dallage n'est pas commencé ». Un accord est finalement trouvé et les entrepreneurs s'engagent au mois de mars 1879 à se mettre à l'ouvrage pour terminer les travaux et construire la sacristie. Il semble toutefois qu'ils n'ont pas été au bout de leur contrat. Le 15 décembre en effet, un arrêté de mise en régie est prononcé pour achever les travaux et les mettre en état de réception en faveur de Victor Janson et Frédéric Bouissou. Cette année-là, les vitraux signés d'Henri Feur sont également posés. Les derniers travaux concernent la construction du clocher attribuée le 2 avril 1882 à Blaise Monteil et Jules Gorses, entrepreneurs à Saint-Céré, pour la somme de 8629,27 francs. Le 30 août, l'architecte modifie son projet initial de flèche en briques et ciment par une flèche en charpente et couverture en ardoise que valide le préfet le 7 avril 1883. Des travaux complémentaires sont encore effectués au clocher en 1904, à la veille de la Séparation de l'Eglise et de l'Etat.

Par la suite, il faut attendre 1968 pour que des travaux d'importances soient engagés : la charpente est alors rénovée et recouverte de tuiles romanes remplaçant les « tuiles crochets » d'origine (tuiles mécaniques plates) ; les enduits extérieurs sont par ailleurs entièrement repris au ciment gris, opération malheureuse qui a sans doute contribué à l'insalubrité actuelle de l'édifice.