L'église Notre-Dame est mentionnée dès 826 dans un diplôme de Louis le Pieux, en compagnie d'une autre église dédiée à Saint-Etienne, aujourd'hui disparue. Elle pourrait constituer le seul édifice conservé d'un éphémère groupe épiscopal du 6e siècle occupant la partie orientale de l'île de Melun.
Robert le Pieux (996-1031) y installe un collège de chanoines et fait reconstruire l'édifice : de cette campagne du 11e siècle subsistent aujourd'hui la nef et le transept (fortement repris au 19e siècle).
Entre 1161 et 1198, le chœur et l'abside sont reconstruits, la nef et le transept sont couverts de voûtes d'ogives. Des chapelles latérales sont ajoutées le long de la nef à partir de la fin du 13e siècle, puis détruites au 18e siècle (1773-1775). La façade occidentale et la tour sud sont remaniées aux 16e et 17e siècles.
L'édifice fait l'objet d'importantes restaurations au 19e siècle, sous la direction d'Eugène Millet (1853-1859).
Le diptyque de Melun a été commandé à Jean Fouquet par Étienne Chevalier (v. 1410-1474), qui occupait des fonctions importantes auprès du roi de France Charles VII (1403-1461). Étienne Chevalier fut secrétaire du roi, puis contrôleur général des finances et enfin trésorier de France à partir de 1452. Le trésorier de France est l’administrateur des finances royales et des domaines royaux et a autorité pour transmettre les ordres de paiement.
Étienne Chevalier, probablement né à Melun, est resté très attaché à cette ville, bien qu’il vive à Paris. Il commande donc ce diptyque pour la collégiale Notre-Dame, principale église de Melun. L’œuvre restera dans cette église jusqu’à la fin du 18e siècle. En 1773, les chanoines veulent réaliser des travaux importants dans la collégiale de Melun. Le démembrement du diptyque et sa vente ont sans doute permis de financer ces travaux.
Cet ensemble de 12 verrières fut exécuté par le verrier Calixte Poupart entre 1950 et 1953, en remplacement de verrières du 19e siècle détruites par les bombardements de la seconde guerre mondiale. Elles constituent un ensemble fondé sur une composition très simple : une figure en pied dans chaque baie, sans bordure, se détachant sur un fond rouge (abside) ou bleu (chapelles latérales).
Chaque verrière est occupée par une figure en pied : la Vierge à l'Enfant dans la baie d'axe, des personnages bibliques aux fenêtres basses de l'abside, des saints aux fenêtres hautes de l'abside et dans les chapelles latérales du choeur. Soit : David (baie 1), Salomon (baie 2), Deborah (baie 3, tenant un phylactère avec une inscription hébraïque), Esther (baie 4, tenant un rouleau avec écriture cunéiforme), Rebecca (baie 5, tenant une jarre), Judith (baie 6, tenant la tête d'Holopherne), saint Ambroise (baie 7), saint Laurent (baie 8, avec son gril), saint Etienne (baie 100, avec la pierre symbolisant sa lapidation), saint Liesne (baie 101), saint Aspais (en évêque, baie 102).
L'iconographie est en partie inspirée par les cultes locaux se réfèrant aux vocables des églises de Melun, pour la plupart disparues (église Saint-Etienne et chapelle Saint-Laurent, dans l'île, église Saint-Ambroise sur la rive gauche, églises Saint-Liesne et Saint-Aspais, la seule conservée, sur la rive droite).
Dans chaque baie est représenté un saint en pied. Baie 17 : saint Louis, vêtu d'un manteau fleurdelysé, tenant le sceptre et la main de justice. Baie 19 : l'empereur saint Henri, avec son sceptre et le modèle de la cathédrale de Bamberg. Baie 21 : saint Jean Baptiste. Baie 23 : Saint Charles Borromée, vêtu en cardinal.
Auteur : Gsell-Laurent (verrier) 4e quart 19e siècle
Ensemble de verrières exécutées en 1986 par Sylvie Gaudin. : Baies 16, 18, 20, 22.
Chaque verrière évoque de façon symbolique un saint. Saint Michel (un tournoiement d'ailes), saint Nicolas (une houlette), saint Barthélemy (le glaive du martyre), saint Vincent (les vendanges).
Quatrième d'une lignée de maîtres-verriers, Sylvie Gaudin est respectivement la fille, la petite-fille et l'arrière-petite fille de Pierre Gaudin, Ernest Jean Gaudin, et Félix Gaudin. Elle est née le 19 juin 1950 à Boulogne-Billancourt, et morte le 27 mai 1994 à Paris. Elle est connue pour les vitraux originaux qu’elle a exécutés en France jusqu'à sa mort précoce, au zénith de son art.