To evaluate the relationship between Self-Rated Health (SRH) and cardiorespiratory fitness (CRF) in a sample of children and adolescents enrolled in official schools in Bogotá, Colombia. A cross-sectional study was performed with 7402 children and adolescents between 9 and 17 years of age. Participants were asked to rate their health based on eight validated questions, addressing the participants propensity for headache, stomach-ache, backache, feeling-low, irritability/bad mood, nervousness, sleeping-difficulties, and dizziness. The choices were "rarely or never", "almost every month", "almost every week", and "more than once a week/about every day". Participants performed the international course-navette shuttle run test to estimate CRF, and cut-off points for age and gender were used to categorize the healthy/unhealthy fitness zone according to the FITNESSGRAM® criteria. Overall, 16.4% of those surveyed reported a perception of irritability/bad mood "more than once a week/about every day", followed by feeling-low and nervousness (both with 9.9%). Dizziness had the lowest prevalence with a percentage of 6.9%. Unhealthy CRF in boys increased the likelihood of headaches by 1.20 times, stomach aches by 1.31 times, feeling-low by 1.29 times, nervousness by 1.24 times, and dizziness by 1.29 times. In girls, unhealthy CRF increased the likelihood of headaches by 1.19 times, backache by 1.26 times, feeling-low by 1.28 times, irritability/bad mood by 1.17 times, sleeping-difficulties by 1.20 times, and dizziness by 1.27 times. SRH was associated with CRF in both genders. Early identification of children and adolescents with low CRF levels will permit interventions to promote healthy behaviors and prevent future diseases during adulthood.