Promilhanes était un prieuré de Marcilhac, dont la première mention connue semble être de la fin du 12e siècle ; en 1318, le prieuré est dit séculier (Clary, 1986). Le premier état de l'église qui nous a été conservé peut dater du 13e siècle. La nef a été surélevée d'un niveau destiné à servir de refuge au 15e siècle. L'édifice a connu de très importants travaux au 19e siècle, et c'est sans doute à ce moment-là que son orientation a été inversée : la clef de voûte du choeur porte la date de 1819, et l'abbé Clary indique que les voûtes de la nef ont été remaniées en 1823, que les chapelles ont été construites en 1838 et le clocher en 1856 ; l'église a pris le vocable de Saint-Pierre et Saint-Paul en 1841 (Clary, 1986).