A l’ouest de Fontainebleau, le quartier de la Faisanderie, situé à la lisière de la forêt, commence à s’urbaniser à partir des années 1950 avec la construction du « Village de la Faisanderie » constitué de quatre barres d’immeubles (Marcel Lods, 1951-1953) destinées à loger l’Etat major du SHAPE (Supreme headquarters allied powers in Europe) de l’OTAN. Dans les années 1960, cette urbanisation se poursuit avec la construction du campus de l’INSEAD (Institut européen d’Administration des Affaires), conçu par l’architecte Bernard de la Tour d’Auvergne, ainsi que celle de plusieurs établissements scolaires (lycée François-Couperin, lycée et collège Jeanne-d’Arc, écoles Saint-Honoré et Saint-Merry). Si dès les années 1940 des terrains rudimentaires d’athlétisme sont praticables à la Faisanderie, l’arrivée des nouveaux riverains et écoliers rend indispensable l’aménagement de cette partie de la forêt en un véritable parc des sports. Ainsi, dans les années 1970, plusieurs équipements sortent de terre, à l’initiative du District urbain de l’agglomération de Fontainebleau-Avon et de la commune de Fontainebleau : d’abord la piscine puis des courts de tennis, le gymnase Lucien-Martinel, un stand de tir à l’arc, des tennis couverts, etc.
La construction de la piscine est décidée par la commune en 1968 bien que le programme soit finalement porté par le District urbain, ancêtre de la Communauté d’agglomération du pays de Fontainebleau, aujourd’hui propriétaire de l’équipement. Ce projet de véritable stade nautique ne fait pas tout de suite l’unanimité au sein du conseil municipal car la ville est déjà dotée de trois piscines : la piscine de la Forêt (1947), celle de la rue d’Avon (ancien lavoir transformé en piscine dans les années 1950) et celle du Camp-Guynemer (installation militaire). Néanmoins, Paul Séramy, maire de Fontainebleau (1959-1992) considère qu’« alors que les sports, et plus particulièrement les sports de l’eau, prennent une place de plus en plus grande dans les établissements scolaires, et compte tenu du climat de notre région nous avons pensé qu’il était nécessaire de construire d’abord une piscine couverte ». Denis Hay est ainsi chargé du projet de construction en 1968. Cet architecte est très actif en Seine-et-Marne dans les années 1960-1970 et en particulier à Fontainebleau où il est l’auteur des tribunes du Grand Parquet (1964), de la station-essence B.P. de la Fourche (1960) et de celle de la Gare (1974, du collège Lucien-Cézard (1965), du refuge de la SPA (1965), de l’usine de traitement des résidus urbains (1968) et de nombreuses opérations de logements (individuels et collectifs). En 1969, Denis Hay, assisté de l’ingénieur Robert Lourdin, rend son projet définitif d’ensemble nautique comprenant un bassin de natation de 25 m, un bassin d’initiation, 60 cabines, des douches, des sanitaires, une plage et un bar. Une seconde tranche de travaux, finalement abandonnée, prévoyait également l’aménagement d’un bassin olympique extérieur. Les travaux débutent en 1970 et prennent fin en 1972, la piscine étant inaugurée le 13 mai. Un an plus tard, Denis Hay est également chargé de la construction du gymnase voisin, adaptation d’un plan-type de COSEC (complexe sportif couvert) dessiné par Erich Kasper et Gérard Leroy, ouvert en 1976 et complétant ainsi l’offre sportive du stade de la Faisanderie.
Alors qu’à la fin des années 1960 de nombreux équipements sportifs sont conçus selon des plans-types agréés par le secrétariat d’Etat à la Jeunesse et aux Sports, conférant à leur architecture une certaine homogénéité, la piscine de la Faisanderie fait figure d’œuvre unique. Elle est édifiée sur une structure de poteaux en béton armé brut de décoffrage au profil pyramidal soutenant des poutres courbes en bois lamellé-collé et contreventée par des pannes. La couverture suit un mouvement ascensionnel particulièrement gracieux conférant une impression d’espace à l’intérieur tout en atténuant la résonnance du son. Les façades sud, est et ouest sont largement vitrées sur la plage extérieure et le jardin environnant, tandis que la façade nord sur rue accueillant les visiteurs est revêtue d’un parement en brique au calepinage particulièrement soigné. Les deux bassins, exposés au sud, sont bordés par des gradins en béton armé permettant d’observer les nageurs. Les espaces d’accueil, vestiaires et sanitaires sont quant à eux situés au nord, éclairés zénithalement par de nombreux lanterneaux.
Entre 2014 et 2016, la piscine de la Faisanderie a fait l’objet d’une vaste réhabilitation confiée à SEDIME. Elle demeure aujourd’hui la seule piscine publique de Fontainebleau – celle de la Forêt ayant été détruite en 2021 et celle de la rue d’Avon comblée et transformée en parking en 1993-1994 – et compte parmi les nombreux équipements sportifs du complexe de la Faisanderie, notamment la récente tribune du stade Philippe-Mahut (Barthélémy Griño, 2016) qui doit accueillir les entraînements d’athlétisme et de tir à l’arc des Jeux Olympiques de Paris 2024. En 2023, la piscine de la Faisanderie reçoit le label « Architecture contemporaine remarquable », attribué par le ministère de la Culture.