Перша згадка про Фонтенбло - у зв'язку з коронацією Людовика VII - відноситься до 1137 р. Документи XII століття цю місцевість в Іль-де-Франс, що загубилася серед дрімучого лісу, називали "Fontene Bleaudi" - "джерело Блоді". Так що джерело Бло - те дивовижне джерело, яке (за переказами) під час королівського полювання знайшов собака по кличці Бло, - і дав назву і лісу, і замку, і місту. Історія Фонтенбло розпочинається з мисливського будиночка, побудованого в XII ст. у багатому дичиною лісу, біля джерела Бло, звідки і пішла назва місцевості Фонтенбло ("фонтен" - по-французьки "джерело"). Пізніше на місці будиночка виросла садиба, а потім був зведений замок, що став надовго королівською резиденцією.
У XII столітті на цьому місці, яке займало більше 17 тисяч га, розташовувався королівський мисливський замок. Традиційна любов до полювання зробила Фонтенбло регулярно відвідуваним місцем, і при цьому чи не кожен король вважав своїм обов’язком зробити свій внесок в поліпшення замкових будівель, перебудовувавши і прикрашаючи їх відповідно до нових смаків.
Найбільш значних перетворень замок зазнав за Франциска I (1494-1547), який побажав перетворити старий "будинок королів" на "Новий Рим", який перевершить розкішшю і красою палаци Венеції, Флоренції і Риму. Будівництво Фонтенбло тривало упродовж 1528-1547 рр. Замість старого середньовічного замку виріс величезний розкішний палац, у вигляді якого втілилися італійські і французькі художні традиції.
Були побудовані ворота, танцювальний зал, каплиця Св. Сатурини, галерея Франциска I, що зв'язала дві групи будівель. Від замку XII ст. збереглася лише одна башня-донжон, в якій колись розташовувалася королівська спальня. Для палацового комплексу Фонтенбло характерні внутрішні двори - відгомін італійської архітектури - і оригінальні підковоподібні зовнішні сходові сходи. Для прикраси королівської резиденції Франциск I запросив італійських живописців, що започаткували так звану "першу школу Фонтенбло».
Мистецтво Фонтенбло середини XVI ст. для якого характерні особлива елегантність, поєднання живопису з декоративними фризами і складним різьбленням по гіпсу, що імітує кольоровий мармур. Художники першої школи Фонтенбло широко включали у свої полотна алегоричні і символічні фігури, що прославляють королів Франції. Ці розписи досі можна бачити на стінах монументальних парадних сходів, в танцювальному залі і королівській спальні, але краще всього вони збереглися в галереї Франциска I, створеною Россо Фіорентино між 1522 і 1540 рр.
До часів короля Франциска I відноситься і створення садово-паркового ансамблю у Фонтенбло. Навколо палацу був розбитий величезний парк "По італійській моді", який, незважаючи на численні пізніші переробки і доповнення, дає уявлення про садово-паркову архітектуру XVI століття. Велика водойма у формі трапеції, що є центром парку, колись використовувалася для всіляких "водяних затій" і забав. У нім були влаштовані фонтани, найбільший з яких прикрашала статуя "Геркулес" роботи Мікеланджело. На штучному острові посеред ставка був споруджений банкетний павільйон.
У подальші віки палац у Фонтенбло неодноразово піддавався значним переробкам. За доброю старою традицією кожен монарх, зійшовши на престол, поспішав прикрасити "будинок королів" чим-небудь новим. Хоча будівельники намагалися дотримуватися проекту, затвердженого Франциском I, час вносив свої корективи.
При Генріху IV (1552-1610) палац піддався новим великим переробкам, якими керував архітектор Амбруаз Дюбуа. Фламандські живописці започаткували "другу школу Фонтенбло". За розпорядженням Генріха IV був значно розширений парк. У нім був проритий канал протяжністю 1200 м, висаджені платани - для Франції тієї епохи велика рідкість, а також плодові дерева. Король Людовик XIII, чиє дитинство пройшло у Фонтенбло, додав до палацового ансамблю залізні сходи. У 1661-1664 рр. Андре Ленотр, придворний садівник Людовика XIV і творець Версальського парку, розбив на місці колишнього Великого парку зелений партер. Сам "король-сонце" мав звичай щорічно проводити у Фонтенбло два осінні місяці, насолоджуючись спокоєм і прекрасною природою.
До часів правління Людовика XV відноситься перебудова південної частини двору Білого Коня і спорудження Великого павільйону, що дістав назву "Ермітаж маркізи Помпадур". При Людовику XVI були в два рази збільшені розміри галереї Франциска I і створений будуар королеви, що складався з трьох салонів, оброблених відповідно до смаків часу. Коли в 1804 р. у Фонтенбло приїхав Наполеон, "будинок королів" уразив його невинною порожнечею. Залишалися одні порожні зали, а уся розкішна обстановка зникла завдяки старанням "громадян" республіки. За розпорядженням Наполеона палац був наново обставлений і прикрашений, і в його стінах імператор Франції приймав римського папу Пія VII, що прибув в Париж для його коронації.
З Фонтенбло пов'язані останні драматичні сторінки історії наполеонівської імперії. 28 квітня 1814 р., попрощавшись з солдатами Старої гвардії, що вишикувалися у дворі, Наполеон назавжди покинув замок. Через роки, знаходячись в засланні на острові Св. Олени, він до останнього дня згадував Фонтенбло - "істинний будинок королів, краще за усіх прикрашений і найвдаліше розташований палац в Європі". Національний музей Фонтенбло зберігає безліч предметів, що належать особисто Наполеону, його дружині, братам і сестрам.
У подальші роки палац Фонтенбло залишався "домашньою" королівською резиденцією. У 1837 р. в стінах палацу відбулося одруження спадкоємця престолу принца Орлеанського з німецькою принцесою. Останній розквіт Фонтенбло доводиться на часи Другій імперії. Імператор Наполеон III відновив покинуту частину парку, відреставрував приміщення палацу, і до 1868 р. Фонтенбло залишався місцем офіційних прийомів, урочистостей і звеселянь імператорської пари.
Сьогодні палац і парк Фонтенбло є національним музеєм, що входить в список об'єктів Всесвітньої спадщини ЮНЕСКО, а частина його за традицією залишається резиденцією глави держави.