The purpose of this study was to examine trends in the body mass index (BMI) and physical fitness of Japanese university students over a period of 26 years and the association between these parameters. We retrospectively collected data on 17,514 students aged 18-19 years attending a university in the years 1984, 1986, 1990, 1991, 1996, 1997, and 2004-2010. The subjects were classified into three body types on the basis of calculated BMI: underweight (BMI<18.5), normal (18.5≤BMI<25), and overweight (BMI≥25). We also calculated the physical fitness score on the basis of 4 fitness-test results (hand-grip power, handball throwing distance, 50-m running time, and 20-m shuttle run count). The time of assessment was categorized into three periods: 1980s (1984 and 1986), 1990s (1990, 1991, 1996, and 1997), and 2000s (2004-2010). The association of physical fitness with body type and period was analyzed using 2-factorial analysis of variance. Descriptive statistics showed that over the 26-year period, moderately increases in the prevalence of underweight and overweight individuals were observed, and the fitness score decreased for both sexes and all body types. A significant interaction between body type and period on physical fitness was observed in boys (P<0.05); underweight and overweight boys showed a greater decrease in physical fitness than normal-weight boys from the 1990s to the 2000s. These long-term data suggest that over 26 years, an increase in the prevalence of underweight and overweight individuals among university students resulted in a decrease in fitness levels to a greater extent in boys.