In this paper, we describe changes in cardiorespiratory fitness among children and adolescents in New South Wales, Australia from 1997 to 2004. Altogether, 4363 children and adolescents were surveyed in 1997 and 3720 were surveyed in 2004. Participants were randomly selected from Grades 4 and 6 in primary school and Grades 8 and 10 in high schools. Cardiorespiratory fitness was assessed on both occasions using the 20-m shuttle run test. There was a very small, but statistically significant, increase in the median number of laps completed for primary (P¼0.02) and high school girls (P¼0.02) and high school boys (P¼0.01); however, the prevalence of adequate cardiorespiratory fitness did not change significantly from 1997 to 2004 for primary or high school boys or girls. Cardiorespiratory fitness was higher among the most socially advantaged boys and girls and this tertile also recorded the greatest increases in all but one group. Over the period 1997 to 2004, the prevalence of adequate cardiorespiratory fitness among students rose slightly in general. It is concerning that the gap between low and high socio-economic tertiles appears to have widened.