Background: Physical fitness is considered an important indicator of health in adolescents. However, in recent years several studies in the scientific literature have shown a considerable lower trend and an alarming worsening of the current adolescents’ physical condition when comparing with previous decades, especially in urban populations. The aim of the current study was to analyse the temporal trend in cardiorespiratory endurance (CRE) in urban Catalan adolescents over a 20-year period (1999–2019). Methods: A cross-sectional analysis study considering the 20-m Shuttle Run test (SRT) results obtained in the last 20 years was carried out. 1,701 adolescents between 15 and 16 years old (914 boys and 787 girls) were divided into four groups, corresponding to consecutive periods of five years (Group 1: 1999–2004; Group 2: 2005–2009; Group 3: 2010–2014 and Group 4: 2015–2019). ANOVA was used to test the period effect on CRE and post hoc Bonferroni analysis was performed to test pairwise differences between groups (p < 0.05). Results: Results showed a significantly lower performance in CRE in both sexes. The percentual negative difference was 0.67%, 9.6% and 7% for boys and 5.06%, 14.97% and 9.41% for girls, when comparing the performance in 20-m Shuttle Run test for the first period, respectively. Conclusions: Results suggest that the physical fitness of Catalan urban adolescents is lower in both sexes when comparing the different analysed periods of time. Therefore, CRE adolescents should be improved in order to help to protect against cardiovascular disease and other health risks in adulthood.