Le moment précis pendant lequel s’est constitué le village de Fleury n’est pas connu, bien que le nom ancien de la localité - Floriacus - en fasse une fondation de la période gallo-romaine. Cette affirmation de Ghislain Brunel, basée autant sur le toponyme que sur la situation du village au sein de la forêt, est corroborée par plusieurs découvertes de mobilier archéologique de cette époque (substructions, tuiles, tessons de céramique, monnaies), qui ont surtout été effectuées à des carrefours de voies forestières. La limite nord-ouest du territoire communal est en outre formée par l’ancienne chaussée romaine qui reliait Paris à Soissons et dont le tracé est à l’origine de l’actuelle RN 2.

Les étapes de la formation de la paroisse n’ont pu également être cernées, même si la consécration de l’église à saint Martin est un signe d’ancienneté. La plus ancienne mention de la paroisse est le don (ou la confirmation du don) de l'"autel" du village vers 1095, par l’évêque de Soissons Hugues de Pierrefonds (1093-1103), à l’abbaye bénédictine Notre-Dame de Soissons, libéralité rapportée par dom Michel Germain, historien de cette grande abbaye de femmes. Dès cette période, l’abbesse va donc lever la dîme en ce lieu. En l’état actuel des connaissances, il n’est pas possible de dire si la paroisse de Fleury s’est transformée immédiatement en annexe de celle de Corcy - autre possession, mais plus ancienne, de Notre-Dame de Soissons. Toutefois, dans les derniers siècles de l’Ancien Régime à tout le moins, le curé de Corcy, prêtre séculier présenté par l’abbesse, est également chargé du desservice de Fleury. Cette double mission a sans doute été difficile à remplir avec rigueur puisque en 1629, les habitants de Fleury vont se pourvoir contre le curé de Corcy afin d’avoir à Fleury un vicaire sédentaire chargé des fonctions curiales. Leur demande est satisfaite, et l’entretien décent de ce religieux est organisé par un jugement de l’évêque de Soissons daté du 24 avril 1630. Cette paroisse du diocèse de Soissons appartient alors au doyenné de Vivières, membre du Grand archidiaconé.

Les remaniements consécutifs à la Révolution font de Fleury au 19e siècle un élément du doyenné de Villers-Cotterêts. À la reprise du culte dans les premières années du 19e siècle, Corcy et Fleury redeviennent desservies par un même religieux. Mais la paroisse de Fleury devient annexe de Dampleux dès le 1er quart du 19e siècle, ce dont témoigne l’épitaphe de Pierre Lefebvre (fixée sur un contrefort du chœur de l’église), mort en 1826 "curé desservant de Dampleux et Fleury". Au début de 1893, la paroisse de Dampleux ayant été confiée au curé de Faverolles, celle de Fleury partage donc son sort. Depuis les regroupements paroissiaux de la fin du 20e siècle, le village de Fleury appartient désormais à la grande paroisse Saint-Nicolas-du-Pays-de-Retz, devenue membre d’un doyenné de Villers-Cotterêts étendu.

Jusqu’à la Révolution française, ce territoire du Valois est situé dans l’étendue de la châtellenie de La Ferté-Milon. Peu avant la Révolution, comme le signale l’abbé Houllier, le village relève de la Généralité de Soissons, de l’Élection de Crépy-en-Valois et du bailliage de Villers-Cotterêts. Il fait aujourd'hui partie du canton de Villers-Cotterêts et de l'arrondissement de Soissons. Avant la suppression du régime féodal, la seigneurie de Fleury, unie à celle de Corcy, et la haute justice sont tenues conjointement par l’abbaye Notre-Dame de Soissons (pour 7/8) et les seigneurs du "fief de la Place" à Corcy, qui possèdent le dernier 1/8. En ce qui concerne la seigneurie foncière, Fleury est un arrière-fief, mouvant du fief de Marolles, ce dernier étant lui-même tenu du roi ou du duc d’Orléans à cause du château de La Ferté-Milon. Il consiste en la ferme de Fleury, des terres et des prés, l’étang du lieu et un petit moulin à blé, enfin en divers droits seigneuriaux dont les moyenne et basse justices. Ce fief, qui avait été la propriété successive de plusieurs seigneurs laïcs - les archives mentionnent à partir de 1473 Jean de Fresnes père et fils, Pierre Pellerin, puis Jean de Hecques -, est adjugé le 26 juin 1531 aux chartreux de Bourgfontaine, qui vont ensuite le bailler à ferme. Mais en 1770, le duc Louis-Philippe d'Orléans (1725-1785), qui réside régulièrement au château de Villers-Cotterêts, forme dans la forêt de Retz un vaste parc de chasse, enclos de murs qui enferment le village de Fleury à l'intérieur de cette enceinte. Conscients des complications variées que ce parc pourrait susciter dans la gestion de leurs biens, les chartreux de Bourgfontaine acceptent par un acte sous seing privé du 16 novembre 1771 de céder au duc leur domaine, fief et ferme de Fleury - sauf l’étang et le moulin - en échange d’une autre propriété. L'acte du 14 mai 1783, qui confirme le précédent accord, permet au duc de réunir l'enclave de Fleury à la forêt de Retz. Un acte du 2 mai 1775 scelle l’acquisition du terrain et des bâtiments du presbytère de Fleury auprès de particuliers, et un autre, du 31 juillet 1775, l’obtention de neuf arpents de terre des prémontrés de l’abbaye Notre-Dame de Valsery, ces biens immeubles étant tous destinés à être réunis par le duc d’Orléans au domaine de Fleury et au duché de Valois.

En 1787-1788, le transport et l’installation de la faisanderie du château de Villers-Cotterêts dans la ferme de Fleury achèvent de lier la destinée de ce territoire au plaisir princier de la chasse.

La Révolution française, qui éclate peu après, infléchit irrévocablement l’histoire de Fleury. Les apanages sont supprimés en 1790, et la saisie du château de Villers-Cotterêts par la Nation rend inutiles le parc de chasse et la faisanderie. L’enceinte du parc, d’abord préservée, est ensuite progressivement détruite, permettant au village de sortir de son enfermement. La ferme est adjugée le 26 janvier 1793 et le presbytère vers juillet 1796 ou peu après. L’Église, moins présente qu’ailleurs depuis les acquisitions du duc d’Orléans, disparaît elle-aussi de la liste des propriétaires fonciers. Le moulin et l’étang - conservés jusque-là par la chartreuse de Bourgfontaine - changent ainsi de mains le 16 mai 1791, partageant le sort des terres de la fabrique et de quelques communautés, qui sont aliénées dans le courant des années 1790 à divers particuliers.

Le village et la vie de ses habitants évoluent tout au long du 19e siècle, sous l’influence des lois et du progrès. C’est ainsi qu’une mairie-école est bâtie au milieu de ce siècle, puis agrandie et améliorée en 1887. La modernisation des moyens de transport désenclave complètement Fleury. Situé sur le tracé de la ligne de chemin de fer Paris-Soissons - construite par tronçons successifs -, le village est desservi par la gare de Villers-Cotterêts dès la fin de 1861, puis aussi par celle de Longpont dès le milieu de 1862. Cette dernière est délaissée quelques décennies plus tard, en faveur de la halte de Corcy plus proche, créée dans le courant des années 1890. Enfin, à la veille de la déclaration de guerre, un bureau téléphonique est établi dans la localité ou sur le point de l’être.

Cette vie paisible est temporairement stoppée par l’éclatement de la Première Guerre mondiale. Peu d’informations sont connues pour les premières années de cette guerre, pendant lesquelles l’agglomération, à l’écart des grandes routes, semble surtout avoir accueilli des troupes qui y cantonnent. Mais la situation change lors des offensives allemandes de 1918 et des contre-attaques alliées. L’historique du 46e régiment d’Artillerie de campagne, unité fort engagée dans la défense opiniâtre de cette zone, signale en particulier à la date du 4 juin 1918 un violent bombardement "dans la région de Fleury". À l’issue du conflit, le village n’est pas détruit, contrairement à plusieurs de ses voisins situés plus à l’est ; ses constructions sont néanmoins endommagées, comme en témoignent les rares dossiers de dommages de guerre conservés.

Au début de l'entre-deux-guerres, le rétablissement de l’agglomération semble avancer rapidement, car la Carte spéciale des régions dévastées mentionne, à la date du 1er décembre 1920, 30 maisons déjà réparées ou reconstruites. La restauration des bâtiments communaux, quant à elle, est confiée en 1919 à la Coopérative de reconstruction de Faverolles, Ancienville, Fleury et Oigny, dont l’architecte est Frédéric Bertrand (1869-1956). Les bombardements subis et le patriotisme des habitants ont valu à la localité d'être citée à l'ordre de l'armée et de recevoir la Croix de guerre par décret du 23 août 1923.