Villeneuve-sur-Yonne est née, en 1163, sous le nom de Villefranche-le-Roi, de la volonté du roi Louis VII (r. 1137-1180) qui désirait protéger les limites du domaine royal face au comté de Champagne. Il acheta aux Prémontrés d’Auxerre le territoire de Villeneuve et plusieurs aménagements virent le jour dont un pont, appuyé sur une île de l’Yonne, des murailles d’enceinte flanquées de tours et des portes fortifiées.
Le fils de Louis VII, Philippe Auguste, fit de Villefranche-le-Roi une de ses huit résidences royales et la dota d’un donjon. Il y tint Parlement en 1204 tandis que Louis IX y résida avant de partir pour la huitième croisade.
Le pont permit l’établissement de relations est-ouest, mettant la ville sur le trajet des marchands circulant des pays de Loire vers les foires de Champagne.
Si la première pierre de l’église fut posée en 1163 par le pape Alexandre III qui posa, la même année, la première pierre de Notre-Dame de Paris, le début de la construction se situe vers 1215. L’église est dédiée à la Vierge comme nombre d’églises du XIIIe siècle, période de développement du culte marial. Son ampleur souligne l’importance de la cité, lieu d’une résidence royale au moment de sa construction.
Les travaux, arrêtés pendant la Grande peste puis la Guerre de Cent ans, se terminèrent à la fin XVIe siècle avec des aménagements Renaissance dont le plus spectaculaire est le portail en forme d’arc de triomphe qui précède.