Une résidence royale a pu exister sur l'île dès le haut Moyen Age. On en trouve des mentions explicites à partir du 11e siècle. Les premiers capétiens séjournent volontiers dans cette place stratégique jusqu'à la conquête du domaine champenois en 1285 : avec Etampes, Orléans et Compiègne, Melun est le principal lieu d'expédition d'actes des souverains avant Louis VI. Un acte de Philippe Ier est donné en 1094 dans la tour de Melun, un autre dans le palais neuf (1100), ce qui laisse penser que ce roi a fait reconstruire le château à la fin du 11e siècle. Une chapelle est attestée dès 1165, par une mention de dédicace en l'honneur de Notre-Dame et de saint Vincent ; il s'agissait sans doute d'une chapelle double. Au début du 13e siècle, le château est profondément remanié par Philippe Auguste. Il demeure résidence royale jusqu'au 15e siècle. Charles V y mène des travaux en 1360-1361 et y dépose une partie de son trésor. Après la guerre de Cent Ans, le roi n'y séjourne plus guère : le château est utilisé comme prison et lieu de garnison. L'édifice est délaissé dès le 17e siècle, son état se dégrade et les établissements religieux s'en servent comme carrière. Au 18e siècle, le château est cédé à la municipalité pour y installer une caserne. Ce projet restant sans suite, les vestiges du logis royal sont loués aux fermiers des coches d'eau en 1743. L'aménagement du port au milieu du 18e siècle provoque le remblaiement des fossés et la démolition des fortifications. Les derniers éléments de l'édifice sont détruits dans les années 1830. Seul le soubassement d'une tour marque encore le site occupé par le château jusqu'au début du 20e siècle. Aujourd'hui, plus aucune trace ne subsiste de cette résidence royale, sinon une citerne chez un particulier.