Dépendant à l’origine de la paroisse de Blancfossé dont elle était un vicariat (Louis Graves, 1843), l’église de Fléchy est placée sous le vocable de Saint Fuscien et Saint Gentien, martyrisés à la fin du IIIe siècle à proximité d’Amiens. Louis Graves (1843) affirme sans citer sa source que l’édifice est construit en 1568, une date qui semble cohérente avec plusieurs marqueurs stylistiques : arc en anse de panier de l'entrée, forme des sablières de la charpente, présence des blochets sculptés, baie à remplage flamboyant du chœur. Bien que les graffitis doivent être considérés avec précaution, la présence de la date de 1547 sur les murs pourrait confirmer une campagne de construction dans la première moitié du XVIe siècle.

Les documents de la série O conservés aux Archives départementales de l'Oise éclairent les différentes campagnes de travaux réalisées au cours du XIXe siècle. En 1816, le conseil de fabrique signale le mauvais état de l'édifice. C’est notamment le clocher et le toit côté nord, tous deux recouverts d’ardoise, qu’il faut réparer de toute urgence : pour financer les travaux, le préfet de l’Oise autorise le conseil municipal à surimposer les habitants les plus aisés.

Une nouvelle série de travaux visant notamment à construire une sacristie attenant au côté nord de la nef débute en 1845. De plus, la couverture d’ardoise est refaite, un nouveau faîtage de zinc est posé, la rampe du pignon de la nef ainsi que le cintre du portail sont réparés, et un petit périmètre de carrelage est restauré avec la pose de grands carreaux de Beauvais. Ces travaux entraînent toutefois des désordres insoupçonnés et de nouvelles réparations sont alors décidées : les murs de la nouvelle sacristie doivent notamment être surbaissés en raison d’un sol "de mauvaise qualité". L'entrepreneur Josué Candillon les exécute en 1848.

En 1882, une nouvelle demande de secours est adressée aux services de l’État pour réparer une fois encore la toiture. Elle est appuyée par l’évêque de Beauvais et par le sous-préfet qui affirment dans une lettre du 3 avril que "les tuiles sont brisées ou pourries, les bois vermoulus" et que "l’eau pénètre à l’intérieur en causant de graves dommages à la voûte". Les réparations ont-elles pu voir le jour ? La série O des Archives départementales de l’Oise ne contient aucune réponse du préfet, qui est "en congé".

En 1897, on entreprend de consolider le clocher afin d’accueillir une nouvelle cloche baptisée "Marie-Louise" en l’honneur d’une bienfaitrice ayant permis la fonte de ce nouvel instrument.

D'après des témoignages oraux, la couverture de l'église est remplacée dans les années 1970. Au début des années 2000 l'intérieur de l'édifice est intégralement repeint.