L'église de Vauchelles-les-Quesnoy, qui date des XVe et XVIe siècles, est mentionnée pour la première fois en 1138 dans une charte où le comte de Ponthieu fait don de l'église au chapitre de l'église collégiale d'Abbeville, en même temps que celle d'Épagnette (IA80011007) (Bacquet, 1992). Plus tard, Dom Grenier cite la présence d'une chapelle en 1343 (Prarond, 1861). Mais aucun élément bâti ne subsiste de cette période et il semble que l'ensemble ait été reconstruit après la guerre de Cent Ans.

Selon l'analyse archéologique de la forme des baies de la nef en plein cintre, et de celles du chœur - plus hautes et en tiers-point avec remplage flamboyant -, la nef serait plus ancienne que le chœur et remonterait au XVe siècle, tandis que le chœur daterait de la seconde moitié du XVIe siècle. Une des verrières du chœur, remplacée au XIXe siècle, portait la date de 1570 (Prarond, 1861). Cette datation était autrefois admise dans la tradition locale de la population, qui estimait que l'église "de cette localité qui n'était alors que l'annexe du petit village d'Épagnette", datait de 1575 (AD Somme ; 99 O 3657). Les deux dates distinguent sans doute la pose des verrières dans un cas, et l'achèvement définitif des travaux ou la date de consécration de l'édifice dans l'autre cas. Le clocher est quant à lui construit de manière plus certaine au cours du troisième quart du XIXe siècle.

Avant cette campagne de travaux, l'église, représentée "d'après nature" par Oswald Macqueron en mai 1850 (AC Abbeville ; B800016201 AB N068), possède une nef de deux travées avec un clocher essenté d'ardoise et couvert d'un dôme (ill.). Le portail occidental, en plein cintre, est surmonté d’une croix. Un mur en brique et les haies permettent de délimiter l’espace du cimetière. À l'époque, les chapelles latérales ne sont pas encore construites. Un second dessin réalisé "d'après un croquis de Gillard" en 1864 (AC Abbeville ; B800016201 AIL 069), présente l'église dotée de chapelles. Elles ont donc été construites dans cet intervalle, entre 1850 et 1864. À la même époque, la sacristie, déjà élevée sur deux niveaux, présente visiblement une architecture plus simple qu'aujourd'hui.

Dans le troisième quart du XIXe siècle, en raison de l'accroissement de la population du village et de la nécessité de réaliser des travaux de consolidation "d’une urgence reconnue par les hommes de l’art" (AD Somme, 99 O 3657), il est envisagé de réaliser une extension de l'église intégrant la reconstruction complète du clocher. La commune ne possédant pas les fonds nécessaires pour réaliser cette extension, les travaux sont financés par plusieurs dons, ainsi que par un impôt extraordinaire et un secours du Département et de l’État.

L’architecte retenu pour réaliser cet agrandissement est Léopold Dingeon. Il dresse les plans et élévations en février 1862 (ill.) et dirige donc la reconstruction du clocher et la partie occidentale de la nef, élevés en pierres issues des carrières de Pont-Rémy (80) et de Saint-Maximin (60). La charpente de la nef est également refaite lors de ce chantier. Mais en 1865, la présence du cimetière autour de l’église gêne l’agrandissement. La sous-préfecture demande au maire de songer à déplacer le cimetière (IA80011024) dans un autre endroit de la commune (AD Somme, 99 O 3657). Le chantier d'extension est achevé en 1866, comme l'indique la date inscrite en chiffres romains sur l’élévation ouest du clocher.

Plusieurs aquarelles d'Oswald Macqueron réalisées d'après nature en juillet 1869 (AC Abbeville ; B800016201 AB 070) et en juillet 1881 (AC Abbeville ; B800016201 AB N071) rendent compte des travaux réalisés. Sur la première aquarelle, la sacristie y est encore présentée comme une construction en brique - état qui est différent sur une autre illustration du 4 août 1881 (AC Abbeville ; B800016201 AB N072). Bien qu'elle reprenne l'emplacement de la précédente, la nouvelle sacristie est construite en pierre de taille et présente des ouvertures polylobées de style néo-gothique. Au pied de l'église, il existait visiblement une mare communale qui a été comblée à une date indéterminée.

Enfin, l’église subit quelques dégâts au cours des bombardements de mai-juin 1940 : la maçonnerie ainsi que les vitraux sont détériorés.