Jusqu'au XVIIIe siècle, Lamothe-Fénelon s'est appelé Lamothe-Massat. L'église était un prieuré non conventuel appartenant à l'abbaye de Souillac depuis au moins le XIIe siècle. Géraud de Massaut, moine de Souillac, en est le prieur en 1253. Le plan de l'abside, avec un hémicycle outrepassé et une travée droite a conduit à croire que cette partie remonte au haut Moyen Âge. Cependant, l'appareil en pierres de taille posées sans joint ne permet pas de la placer avant la seconde moitié du XIIe siècle. La façade occidentale a été reconstruite au XIVe siècle, ainsi que l'élargissement de la nef vers l'ouest. La chapelle nord a été reconstruite dans les années 1490, sans doute par Jean de Salignac, seigneur du lieu, qui demande à être enterré dans la chapelle, nouvellement bâtie, de Notre-Dame-de-Pitié, en 1497. La nef a été voûtée dans les dernières années du XVe siècle ou au début du XVIe siècle. Au cours des fouilles de 2011 dans la chapelle nord, des maçonneries antérieures à la chapelle actuelle ont été découvertes. Elles devaient former un transept avec la chapelle sud.