The aim of this study was to estimate genetic and environmental influences on the longitudinal evolution of leisure-time physical activity habits from adolescence to young adulthood. Data were gathered at four time points, at mean ages 16.2, 17.1, 18.6, and 24.5 years. At baseline, the sample comprised 5,216 monozygotic and dizygotic twins, born 1975–1979, and, at the last follow-up point, of 4,531 monozygotic and dizygotic twins. Physical activity volume was assessed as frequency of leisure-time physical activity and participants were categorized into three groups: inactive, moderately active, and active. Genetic and environmental influences were estimated using a multivariate, longitudinal Cholesky decomposition with a ‘multifactorial liability threshold’ approach. The results suggest that, in both sexes the heritability of leisure-time physical activity remained moderate (~43–52%) during adolescence, declining to ~30% in young adulthood. Shared environmental influences increased from adolescence (~18–26%) to young adulthood (43% in men and 49% in women). Specific environmental influences remained relatively stable during the total follow-up (~20–30%). New genetic, shared, and specific environmental influences at every follow-up point were suggested by the low correlations across occasions. In conclusion, the study demonstrated gender differences in genetic influences in the evolution of leisure-time physical activity habits from adolescence to young adulthood. However, shared environmental influences, especially in women, were crucial in explaining longitudinal changes in leisure-time physical activity. These outcomes emphasize the need of gender-specific measures to promote physical activity habits during young adulthood.