Livré en 1999, le gymnase Nelson-Paillou est consacré à la pratique du volley-ball, du badminton et du basket, mais surtout à celle du handball, sport phare de la ville de Créteil. Ainsi est-il baptisé dès 1997 du nom de Nelson Paillou (1924-1997), en hommage au handballeur et ancien président du Comité national olympique et sportif français puis Président de la Fédération française de Handball (1924-1997). En 2017, la commune est labellisée « Ville active & sportive », confirmant l'intérêt certain de cet équipement, d'un point de vue architectural mais également sportif.
La vaste nef est totalement dédiée aux sportifs, tandis que les autres fonctions sont repoussées sur les extérieurs. À l'ouest, l'entrée est encadrée par deux volumes indépendants, aux dessins distincts : le premier, une petite tour ellipsoïdale, abrite les vestiaires. Les lignes courbes qui le caractérisent évoquent le mouvement, le jeu. Le second, un parallélépipède, héberge la loge du gardien et la salle des arbitres. Ce cube aux arêtes saillantes n'est pas sans évoquer cette fois la rigueur des règles sportives. Les locaux techniques sont disposés à l'est, ouverts sur une cour anglaise qui les sépare du bâtiment principal. Les spectateurs quant à eux prennent place sur les gradins de béton pouvant accueillir jusqu'à 330 personnes. Ces tribunes forment de larges emmarchements se prolongeant à l'extérieur, vers l'entrée située à l'ouest, à peine interrompus par la paroi de verre. Une passerelle métallique relie les vestiaires aux gradins et au terrain central, évitant ainsi une emprise au sol qui viendrait rompre les circulations et réduirait les espaces.
Cette continuité entre l'intérieur et l'extérieur, qui agit comme leitmotiv architectural, est la marque des architectes Séverine Stoffel et Stéphane Lefebvre, lauréats du concours lancé en 1995. Ils créent ainsi une illusion visuelle en floutant la limite entre le dehors et le dedans grâce à une structure de verre et métal. En effet, les parois sud et nord sont entièrement composées de pavés de verre, permettent de créer un espace totalement ouvert à la lumière, même si un nécessaire pare-soleil a été intégré à la structure.
Courbe, la toiture repose sur quatre bipoutres de grande portée disposées dans la longueur du gymnase qu'elles dépassent de peu, formant un auvent. Cette toiture dessine un profil dynamique, comme un écho à la tension physique libérée par la pratique sportive. L'édifice est naturellement ventilé et éclairé de surcroît grâce aux lanterneaux courant sur toute la longueur des bipoutres. Enfin, véritable choix esthétique, l'architecture du gymnase se révèle tout particulièrement la nuit : les rampes lumineuses installées dans les façades illuminent les parois de verre translucides, conférant au gymnase un aspect phosphorescent saisissant et agissant comme un repère dans la ville.
Mi-intérieur, mi-extérieur, le gymnase Nelson-Paillou s'impose, selon ses architectes, comme une « anti-boîte » transparente et légère. Visuellement grand ouvert, le bâtiment inscrit visiblement le sport dans la ville. Il s'intègre enfin parfaitement dans l'ensemble immobilier qu'il a contribué à faire naître.