La première mention connue de l'église apparaît avec celle de son recteur en 1342 (Clary, 1986). Elle avait pour annexe l'église Saint-Hilaire et dépendait du Chapitre de Cahors jusqu'à la Révolution. Cette église, dont il ne reste plus traces aujourd'hui, est dans un état "remarquable" lors de la visite pastorale de Mgr Bardou en 1848 (archives diocésaines). La description sommaire qui en est faite permet toutefois de se faire une idée de cet édifice, visible également sur le cadastre de 1829 : le chœur est "vouté en plein cintre", la nef a "un plafond de lambris", les deux petites chapelles sont voûtées et le tabernacle est "bien ainsi que le tableau qui le domine".

Moins de vingt ans plus tard elle est détruite au profit d'une nouvelle église, plus vaste et plus au goût du jour, conçue par un architecte dénommé Lafon mais qui n'a pas été identifié à ce jour. La dépense s'élèvera à 20700 francs, entièrement supportée par la fabrique alors que la paroisse ne compte qu'un peu plus de 300 habitants. En octobre 1866, le conseil municipal octroie à la fabrique "la cession des matériaux de la vieille église" afin de terminer la nouvelle en cours de construction : l'église médiévale est donc encore en service jusqu'à cette date-là, le nouvel édifice ayant en effet été bâti à proximité de l'ancien et non à son emplacement même. En contrepartie la fabrique s'engage à céder la nouvelle église à la commune, à titre gratuit. Le gros œuvre, dû à l'entrepreneur Léris, semble achevé en 1868, date portée sur la clef de voûte de la 1ère travée. L'abbé Alexis Artoux, curé de Paillas de 1864 à sa mort en 1873 et dont le nom figure sur la clef de la 2e travée, en est probablement l'instigateur.

En septembre 1870, le conseil municipal de Lalbenque vote un emprunt de 2000 francs pour aider la fabrique à construire le clocher. Cette somme a-t-elle été vraiment versée ? On en doute car en avril 1876 le clocher n'est toujours pas achevé faute de moyens selon l'abbé Laquièze, nouveau curé de Paillas. Ce dernier écrit à l'évêque que "ce travail devrait être exigé [...] par M. Tourette". A la même période l'architecte départemental Tourette suit en effet le chantier de construction du clocher de l'église Saint-Quririn de Lalbenque et il aurait ainsi pu être sollicité pour achever celui de Paillas. L'évêque appuie alors la demande de la fabrique auprès du préfet pour l'octroi d'un secours de 2700 francs. Le clocher semble avoir été achevé au cours des deux années suivantes car la grosse cloche est fondue en 1878.

En 1883 le décor peint est exécuté par Henri Petit (Montauban, 1830-Verfeuil, 1906) et en 1885 les vitraux du chœur sont posés.