L’église paroissiale est attestée en 1301 dans le Pouillé de la province de Reims. Elle relève du doyenné de Moreuil et du diocèse d’Amiens. Comme pour de nombreuses paroisses environnantes, elle subit des dommages importants au cours des Guerres de Cent Ans. Elle est ainsi reconstruite dans le premier tiers du XVIe siècle, à l’initiative de Robert de Lannoy également seigneur de Folleville depuis 1478. À sa mort en 1513, sa veuve puis son fils François poursuivent les travaux. L’église de Paillart est achevée à la même période que celle de Folleville, dans le second quart du XVIe siècle : il est possible de le déduire d’après les armoiries datées entre 1518 et 1530 visibles sur les verrières réalisées par Mathieu Bléville.

La tour du clocher et le chœur sont les premières parties achevées. Ce dernier présente un vocabulaire à la limite des styles gothique tardif et Renaissance tant dans le couvrement (voûtes d’ogives à liernes, nervures réticulées, retombées en pénétration) que dans le percement de vastes ouvertures (baies composées de plusieurs lancettes) au remplage flamboyant (soufflets, mouchettes). Le portail sud remarquablement orné mêle également ces deux styles : arcade polylobée, niches surmontées de dais finement ouvragés, contreforts couronnés par des pots à feu, lancettes trilobées aveugles.

La façade occidentale semble avoir été remaniée au XVIIIe siècle d’après la forme classique de l’entrée surmontée d’un simple fronton triangulaire interrompu par une niche et soutenu par des pilastres peu saillants.

D’importants travaux sont engagés au cours du XIXe siècle. D’après les documents de la série O des Archives départementales de l’Oise les toitures du chœur qui étaient en tuile sont remplacées par de l’ardoise en 1834. Un lattis neuf est également fixé sur le couvrement de la nef. En 1840 des travaux sur les toitures du chœur sont réalisés. Le 12 juin 1842 le conseil municipal se réunit en urgence face à la nécessité de réaliser des travaux de maçonnerie : il faut reconstruire la voûte en bois de la nef, la charpente du clocher, remplacer des ardoises de la toiture, changer certaines poutres au-dessus des voûtes du chœur et refaire la toiture de la chapelle de la Vierge. Ces restaurations sont exécutées par les entrepreneurs Baticle et Pillon.

En 1870 les soubassements de la nef sont restaurés en pierre de la Faloise (80) par Adrien Judenne, maçon à Folleville. En 1876 un ouragan détruit une partie de la toiture qui est refaite.

Au cours du XXe siècle, les travaux ont essentiellement concerné les couvertures (clocher en 1906, versant nord et chœur en 1921, puis en 1926).

En 1992, l'église est classée au titre des Monuments historiques (PA00114983).