L'église Saint-Aspais est attestée à partir de 1080. Sa fondation est probablement liée à l'extension de la ville sur la rive droite de la Seine. On ne sait rien de l'édifice avant le 15e siècle. Le clocher, ébranlé lors du siège de Melun par les Anglais en 1420, fut réparé en 1422 et reconstruit à partir de 1469, au nord de l'église. A la fin du 15e siècle, on décida la reconstruction de l'église, jugée trop petite. A cette fin, le presbytère voisin fut abattu en 1506. A partir de 1517, la fabrique fit appel à Jean de Felin pour construire le choeur. Cet architecte parisien, auteur de la tour de Saint-Jacques-de-la-Boucherie, imprima à l'édifice le style flamboyant très orné développé par Martin Chambiges à Sens, Beauvais et Troyes. Les travaux avancèrent assez vite : à l'automne 1519, le niveau du tas de charge des voûtes du vaisseau central était presque atteint. On connaît le nom de deux maçons alors employés sur le chantier : Pierre Godin et Germain Fannier ou Faunier. Mais la progression fut interrompue par un procès entre l'architecte et la fabrique. Les travaux ne reprirent qu'en 1545 : le maître-maçon Jean François acheva le choeur de Saint-Aspais sur les plans de Jean de Felin. A la suite d'un effondrement partiel des voûtes en janvier 1673, Daniel Gittard mena une importante campagne de réparations en 1675-1683. Les travaux furent adjugés en 1677 à Isambert Simon, Jean Gourjouron et Gilles Le Comte. Un nouvel effondrement s'étant produit en août 1677, le chantier fut repris par Nicolas Sueur. Une nouvelle dédicace eut lieu en juillet 1679, avant la réception des travaux par Gittard en 1683. Des compléments furent apportés par le charpentier Bonneau en 1698, et par les maçons Etienne et Jacques Thévenon en 1703. Au 18e siècle, le dôme du clocher fut reconstruit. En 1793, le culte fut interrompu à Saint-Aspais, utilisée comme fabrique de salpêtre. L'église fut réconciliée en 1797. Une importante campagne de restauration, accompagnée de l'édification d'une sacristie au nord, fut menée par l'architecte de la Ville Buval en 1868-1869. L'édifice fut fortement endommagé en août 1944. La restauration fut menée par Albert Bray de 1945 à 1956, puis par Jean Creuzot. Dès 1951-1952, la partie nord fut rendue au culte. L'église fut solennellement inaugurée par Mgr Debray en juillet 1960. La dernière campagne de restauration menée à Saint-Aspais est celle de Jacques Moulin en 1991.