Dans les années 1960, alors que la France accuse un net retard en la matière, les collectivités s’'équipent massivement de piscines afin de populariser l’'apprentissage de la natation mais aussi dans un objectif de loisirs populaires. La commune de Villejuif décide ainsi la construction d'’une piscine et achète en 1966 des terres agricoles situées au sud de la ville dans les quartiers de logements neufs, face au groupe scolaire et au stade Karl-Marx, afin d'’y compléter l’'offre sportive. Pour le maire Louis Dolly, membre du Parti communiste français, ce projet est un véritable manifeste politique. Ainsi, le conseil municipal confie la construction d’'un stade nautique à Paul Chemetov et Jean Deroche, membres de l'’AUA (Atelier d’'urbanisme et d’'architecture). L'’atelier fondé en 1960 est alors particulièrement sollicité par les communes de la « banlieue rouge » pour son engagement dans l'’architecture sociale. Chemetov et Deroche s'’adjoignent l'’expertise de Miroslav Kostanjévac, ingénieur collaborant régulièrement avec l'’AUA. Au même moment, les trois hommes mettent d’'ailleurs au point le prototype d’'une piscine à bassins multiples construite à Corbeil-Essonnes (1965-1967) dont le modèle sera ensuite décliné à quatre reprises jusqu'’en 1972 (à Argenteuil, Champigny-sur-Marne, Epinay-sur-Seine et Châtillon-Malakoff), indiquant l'’engouement des collectivités pour cet équipement industrialisé. A l'’inverse, les communes de Villejuif et d'’Aubervilliers (stade nautique Marlène-Peratou par Jean Perrottet et Jacques Kalisz), dont les projets de piscines confiés à l'’AUA sont contemporains, s’'affranchissent du plan-type pour offrir un bâtiment unique en son genre. Le chantier du stade nautique Youri-Gagarine démarre dès 1967 et se déroule en un temps record, l'’équipement étant inauguré en septembre 1969 en présence de Georges Marchais.

Le souci premier des architectes a été de concevoir un bâtiment en harmonie avec le groupe scolaire, le gymnase et le stade Karl-Marx situés juste à côté, œuvres majeures d’André Lurçat datant de 1933. Cet objectif a dicté l’esthétique générale de la composition et le choix du béton brut de décoffrage en façade. Le terrain étant relativement exigu et le programme particulièrement ambitieux, les architectes dessinent un bâtiment complexe aux niveaux multiples, dont la fonction de chaque volume est affirmée en façade. En effet, le stade nautique compte quatre bassins : un bassin d'initiation (25 x 15 m), un bassin d'apprentissage (12,5 x 12,5 m), un bassin olympique (50 x 20 m) et une fosse à plongeon (16,10 x 16,50 m) dotée de plongeoirs de 3,5 et 10 m. Les deux premiers bassins sont abrités dans deux volumes couverts tandis que le bassin olympique et la fosse à plonger sont édifiés en plein-air. Les espaces intérieurs comportent également un bar, des bureaux, des salles de réunion, des cabines de vestiaires, des sanitaires et une infirmerie. Les volumes abritant les bassins sont couverts par des coques en béton précontraint à double courbure dégageant une portée de 27 m de longueur du procédé Silberkühl, alors particulièrement novateur. La fosse à plongeon et le bassin olympique sont quant à eux bordés de gradins pouvant accueillir 600 spectateurs, tirant parti de la dénivellation entre les deux bassins. Enfin, la façade sur rue du stade nautique est ornée d’un bas-relief sculpté dans le béton de Paul Foujino, artiste collaborant régulièrement avec Paul Chemetov. En effet, l’AUA apprécie particulièrement le concept de synthèse des arts et sollicite l’intervention d’artistes. Il s’agit également d’une composante importante pour la municipalité qui, sans consulter les architectes, commande une mosaïque à Roland Brice, élève de Fernand Léger, en 1974. Cependant dès les années 1980 cette mosaïque se détache d’elle-même à la suite d’intempéries.

Fait assez rare pour être souligné, l’opération de réhabilitation-extension du stade nautique est réalisée par son propre concepteur, Paul Chemetov, entre 2005 et 2009, garantissant le respect et la compréhension de l’édifice original dans le nouveau programme. Cette réhabilitation a consisté d’abord en la mise aux normes d’accessibilité, à la conformité des bassins et des installations techniques, mais aussi à l’imbrication de nouveaux volumes afin d’agrandir les espaces intérieurs (accueil, vestiaires, cafétéria) et d’installer des espaces ludiques, notamment une pataugeoire. Enfin, Chemetov réalise la couverture de la fosse à plonger afin de permettre son utilisation en toutes saisons. Ces adjonctions ont été traitées en verre, en métal et en bois, permettant la lisibilité de l’intervention par rapport aux structures en béton d’origine. Enfin, dans une démarche environnementale, le système de chauffage a été remplacé par de la géothermie. La qualité de ces installations a valu au stade nautique Youri-Gagarine d’être désigné site d’entraînement pour la natation lors des Jeux Olympiques et Paralympiques de Paris 2024.