Selon la tradition, l'église de Nemours a été fondée pour recevoir une relique de Saint Jean Baptiste. Au retour de la 2eme croisade, vers 1145, Gautier de Nemours, chambellan du roi de France Louis VII le jeune, accueille sur ses terres des religieux de l'ordre de Saint Augustin, qui venaient de Sébastre (Samarie) en Palestine et porteurs de cette vénérable relique. Ils font construire une église, à partir de 1170, au nord de leur monastère. La partie la plus ancienne pourrait être le clocher-porche qui s'ouvre sur sa base par une vaste arcature.

Les archivoltes du porche semblent encore romanes, mais le clocher a probablement été agrandi et surélevé aux XIIIe, XIVe siècles.
L'église a probablement souffert, comme la ville elle-même, des évènements de la guerre de Cent Ans. Au début du XVIème siècle, elle devait être très délabrée lorsqu'il a été décidé de la reconstruire.

Entre 1510 et 1550, le chevet, le chœur, les chapelles et l'amorce du transept sont construits.

À la porte de l'actuelle sacristie, un bénitier porte la date gravée de 1547. Les travaux sont arrêtés pendant la seconde moitié du XVIème siècle, probablement à cause des Guerres de Religion et par manque d'argent.
La consécration de l'église a lieu le dimanche 8 octobre 1595.
La nef et les bas-côtés ont dû être commencés avec des piliers et des colonnes torsadées. La couverture de la nef était plus basse que celle qui existe aujourd'hui, une trace visible à l'intérieur de l'église, le long du mur du clocher, au-dessus de la tribune des orgues l’attestent.


À partir de 1631, les travaux destinés à achever l'église entre le chevet et le clocher-porche vont reprendre. On profite alors de la présence du chantier royal proche de Nemours. Gobert, architecte du roi à Fontainebleau, établit des plans: fenêtres hautes dans la nef et charpente en bois, à l'imitation des voûtes en pierre. Elles sont exécutées par le maître-charpentier Claude Gautrot demeurant à Nemours. Les travaux sont achevés vers 1650.


L'église de Nemours, classée « Monument Historique » en 1841, est déclassée en 1894. Inscrite à l'inventaire supplémentaire des Monuments historiques le 17 juin 1928, elle fut de nouveau classée « Monument Historique » en 1977.