Vechiul castel aflat pe acest loc era deja folosit în ultima parte a secolului al XII-lea de regele Ludovic al VII-lea, căruia Thomas Becket i-a dedicat capela. Fontainebleau era una dintre reședințele favorite ale lui Filip Augustus (Filip al II-lea) și Ludovic al IX-lea. Creatorul actualului edificiu a fost Francisc I, în timpul căruia arhitectul Gilles le Breton a construit cea mai mare parte a clădirilor din "Cour Ovale", incluzând "Porte Doree", intrarea sudică. Regele i-a invitat de asemenea în Franța pe arhitectul Sebastiano Serlio și pe Leonardo da Vinci. Galeria lui Francisc I, cu frescele ei înrămate în ștuc de către Rosso Fiorentino, realizate între 1522 și 1540, a fost prima galerie din Franța bogat decorată.