La commune des Pavillons-sous-Bois, officiellement créée en 1905, fonde son premier club sportif en 1913, le Stade de l'Est Pavillonnais (SEP). D'abord consacré à la pratique du football et de la course à pied, il se développe tout au long du XXe siècle et demeure aujourd'hui l'association sportive la plus importante de la ville. Après avoir occupé des terrains provisoires, le SEP s'installe en 1939 au lieu-dit de la Mare-aux-Oignons, à la limite sud de la commune. En 1941, la municipalité fait l'acquisition des terrains en question afin d'aménager un vaste parc des sports. Ce projet s'inscrit d'abord dans l'élan constructif d'équipements sportifs amorcé dès l'entre-deux-guerres par les municipalités de petite couronne et le département de la Seine, poussés par la nécessité hygiéniste et visant un objectif social. Sous le gouvernement de Vichy, ce mouvement prend de l'ampleur, encouragé par le Commissariat général à l'éducation générale et aux sports, pour lequel la pratique sportive et l'éducation physique des jeunes participent d'une idéologie politique de régénération et de puissance de la Nation. Les moyens engagés dans ce sens par le gouvernement de Vichy sont considérables ; ils consistent en la modernisation des installations existantes mais aussi dans la construction de centre scolaires d'éducation physique (CSEP) et de grands parcs sportifs de plein-air. Les projets sont nombreux et ambitieux, mais faute de moyens financiers, le stade des Pavillons-sous-Bois sera l'un des rares à être effectivement mis en oeuvre.
Confié à l'architecte parisien Henri Larrieu (1902-1977), le projet de parc des sports pavillonnais comprend, sur une superficie de 50 000 m², un gymnase avec des vestiaires, un terrain de gymnastique, un terrain de football de championnat doté de tribunes et de gradins, une piste d'athlétisme de 400 m, des terrains d'entrainement de football, de basketball, des courts de tennis et une piscine de plein air. L'ensemble, particulièrement ambitieux et donc onéreux, doit être construit en plusieurs tranches successives. Dès 1941, la première tranche de travaux est réalisée : il s'agit des terrains de sports et des tribunes du terrain de football. Au sortir de la seconde Guerre mondiale, le gymnase est enfin mis en chantier et ouvre ses portes en 1949. Sa réalisation est alors particulièrement remarquée pour son élégance dans la presse spécialisée. Ce n'est qu'en 1957 que les deux ailes abritant les vestiaires, dessinées par l'architecte plus de 15 ans auparavant, sont adjointes au gymnase. Les autres équipements prévus en 1941, notamment la piscine, ne seront pas réalisés faute de financement. Il faut attendre les années 1980 pour que le complexe sportif soit augmenté d'un bâtiment polyvalent au sud du gymnase puis par des tennis couverts. Entre 2012 et 2014, la ville confie à l'Atelier 2A+ la rénovation complète du gymnase à des fins d'isolation et de mise aux normes d'accessibilité PMR. Cette rénovation est réalisée dans un grand respect de l'édifice d'origine, tant du point de vue technique qu'esthétique : les bâtiments préfabriqués de stockage qui parasitaient le gymnase sont démolis, le bardage en bois est renouvelé, le double vitrage reçoit des menuiseries en bois et aluminium, et les couvertures sont refaites à neuf en bac acier. En 2023, le gymnase reçoit le label « Architecture contemporaine remarquable » (ACR), attribué par le ministère de la Culture aux réalisations architecturales de moins de 100 ans.
La spécificité du gymnase du stade Léo-Lagrange tient particulièrement dans sa mise en oeuvre technique. En effet, l'édifice est entièrement conçu en bois concernant l'ossature, la charpente, le bardage extérieur et les menuiseries. La charpente est constituée de poutres-échelles de 16,5 m de portée, soutenues par des poteaux s'élargissant de la base vers le sommet et formant un chapiteau qui supporte les fermes. A l'intérieur, cette structure, qui rappelle visuellement l'architecture industrielle en métal, permet de dégager une superficie importante au sol. Ainsi, le bâtiment est divisé en deux espaces par la présence de la file de poteaux : côté est se trouve un vaste plateau de gymnastique et de basket et côté ouest une piste de saut. Les ailes du gymnase sont quant à elle réservées aux vestiaires et aux sanitaires. Ces espaces sont également baignés de lumière naturelle grâce à la façade principale, entièrement vitrée, au large bandeau vitré de la façade ouest et aux grandes baies des pignons. Toutes ces ouvertures sont dotées d'huisseries à petits bois de mêmes dimensions apportant une grande cohérence esthétique à l'ensemble et un rythme harmonieux. A l'extérieur également, le gymnase s'inscrit dans le concept et l'esthétique du Mouvement moderne par la rationalité de son plan et l'écriture de sa façade. Les volumes aux lignes épurées d'une grande simplicité permettent d'en deviner le plan, mettant en exergue la salle de gymnastique, à la hauteur sous plafond plus importante et à la façade magnifiée par la succession des poteaux inclinés soutenant le débord du toit. Enfin, le bardage en bois concourt à l'esthétique et à l'équilibre des façades par sa linéarité, dont la couleur tranche avec les menuiseries blanches, tout en réchauffant les espaces intérieurs. Ce type de réalisation entièrement en bois, d'une grande élégance technique et esthétique, a déjà été expérimenté par l'architecte peu après la fin de la guerre, pour la construction de maisons de vacances dans l'Yonne et en vallée de Chevreuse et semble trouver ici son apogée dans un équipement public.