Un lieu de culte est évoqué au VIe siècle par Venance Fortunat qui raconte comment l’évêque saint Germain vint visiter une petite église du village nommé alors BRADEIA dans le diocèse de Paris.
Cette petite église, vraisemblablement le « Vieux Moustier » mentionné dans les sources écrites, fonctionne parallèlement à l’église Saint-Étienne pendant des siècles. L’édifice se trouvait sur l’emplacement actuel de la place Gautier. Elle a servi au culte et des notables y étaient encore inhumés jusqu’au XVIIe siècle. Puis, elle sert d’école, avant de se dégrader rapidement, au point de ne plus apparaître sur le plan de la ville en 1736.
Durant le haut Moyen Âge, un grand cimetière entourait ce petit édifice et s’étendait de la rue de la Madeleine actuelle jusqu’à l’impasse Dîmeresse.
En 2012, la réduction du chœur sur une seule travée au lieu de trois et l’installation d’un chauffage central au sol ont entraîné des travaux de remaniement du dallage. C’est à cette occasion que d’importantes découvertes ont été faites dont une double base de colonnettes, vestige d’un édifice ancien situé à 40 cm sous le niveau actuel de l’église. Son aspect et sa disposition permettent de dater cette structure du milieu du XIIe siècle, soit environ une cinquantaine d’années avant le début de la construction de l’église actuelle.
Y a-t-il eu un édifice plus petit, qui n’aurait perduré que quelques années avant de laisser la place à un projet plus ambitieux ? Ou y aurait-il eu un repentir ?
Dans tous les cas, on attribue à Robert II de Dreux, seigneur de Brie, le début de l’édification (à la fin du XIIe siècle) de l’église actuelle à l’emplacement de l’ancien cimetière.
Par son testament, la reine Jeanne d’Évreux, dame de Brie-Comte-Robert, fonda une rente en faveur de l’église, afin de faire dire des services religieux perpétuels, pour son défunt mari, le roi Charles IV le Bel. Si elle a pris part à l’entretien de l’église ou à sa réfection, c’est de façon bien modeste : on retrouve en effet peu d’éléments d’architecture du XIVe siècle hormis le deuxième niveau intérieur au dessus du portail. Il n’existe d’autre part, à notre connaissance, aucune trace de frais concernant les travaux sur l’église dans ses comptes.
En janvier 1350, on y célébra le mariage de Philippe VI de Valois , âgé de 56 ans, avec Blanche de Navarre, nièce de Jeanne d’Évreux, qui n’en avait que 17 !
C’est le deuxième dimanche après Pâques de l’an 1363, qu’eut lieu la dédicace de l’église, par l’évêque de Paris, Jean de Meulan, ancien archidiacre de la Brie. À cette date, l’église semble être achevée.
Jeanne d’Évreux mourut le 4 mars 1371, dans son château de Brie. Après un service solennel, célébré à l’église Saint-Étienne, son corps fut transporté le Samedi saint à Paris puis à la basilique royale de Saint-Denis.