Les maçonneries de l’élévation nord de l’église ont certainement été réalisées à partir de pierres provenant de l’ancienne cité antique de Vendeuil. Cette dernière aurait périclité après les migrations de population du IIIe siècle et la population se serait déplacée un peu plus au nord, sur son site actuel (Société historique de Breteuil, 2006). D’après des témoignages oraux, la présence du même mortier sur les sarcophages mérovingiens découverts dans le cimetière ainsi que dans certaines parties des maçonneries de l’église indiquerait qu’une première construction aurait été édifiée au cours du Haut Moyen Âge, à partir du Ve siècle. Malgré l’absence de sources, la mise en œuvre en moellons visible aujourd’hui correspond à une construction au moins antérieure au XIe siècle. L’encadrement cintré d’une porte aujourd’hui comblée témoigne de cette ancienneté. En 1049, une bulle du pape Léon IX cite l’église de Vendeuil parmi les paroisses sur lesquelles l’abbaye de Breteuil détient un droit de patronage, attestant de son existence à cette période.

D’après l’analyse stylistique, une importante campagne de travaux est menée au XIIIe siècle. Des maçonneries de la nef sont reprises et le chœur est reconstruit avec un chevet plat et des voûtes d’ogives. C’est toutefois au XVIe siècle que l’église est presqu’entièrement réédifiée. Une tour de clocher massive est adjointe à l’ouest (l’inscription visible sur le contrefort à droite du portail indiquerait le nom du maître-d’œuvre) tandis que deux chapelles sont édifiées entre la nef et le chœur. Les baies de ce dernier sont remaniées et dotées d’un remplage flamboyant.

Comme le renseignent les documents de la série O des Archives départementales de l’Oise, l’église bénéficie de nombreuses campagnes de travaux au cours du XIXe siècle : la couverture en tuile est remplacée par de l’ardoise de Fumay, les charpentes sont renouvelées, les parties hautes du chœur sont rebâties en brique par l’architecte amiénois Delefortrie et la chapelle sud est réédifiée entre 1890 et 1893 par l’entreprise d’Ulphi Candillon (Fransures, Oise). Des peintures murales ornent le mur-pignon de la chapelle sud et celui du chevet. Elles ont pu être réalisées au XIXe siècle mais leur état ne permet pas de l’établir avec certitude.

Dans la seconde moitié du XXe siècle la porte côté sud est comblée et une nouvelle ouverture est percée dans la tourelle d’accès au clocher juste à côté.

Les dernières restaurations dont l’édifice a bénéficié remontent aux années 2009-2010 : l’un des contreforts du clocher a été consolidé, les façades nord de la nef et du clocher ainsi que les façades ouest et nord de la chapelle nord ont été reprises.