This study examined the association between cardiorespiratory fitness (CRF) levels and lifestyle factors in a representative sample of Greek schoolchildren. In 2015, a health survey was carried out in 177 091 participants 8–17 years of age. Dietary habits, sleeping hours, physical activity (PA), and sedentary activities were assessed through self-completed questionnaires. CRF was evaluated with a 20-m shuttle run test. Insufficient dietary habits were greater in boys and girls classified as having low CRF than in their peers with healthy CRF. Skipping breakfast (odds ratio (OR), 0.82; 95% confidence interval (CI) 0.79–0.85), fast food consumption (OR, 0.70; 95% CI 0.68–0.72), and regular sweet intake (OR, 0.79; 95% CI 0.76–0.82) decreased the odds of having a healthy CRF level. An increase in age by 1 year (OR, 0.71; 95% CI, 0.70–0.72), overweight/obesity (OR, 0.30; 95% CI 0.29–0.31), and insufficient sleep duration (OR, 0.74; 95% CI 0.72–0.76) decreased the odds of a healthy CRF level, whereas sufficient dietary habits and adequate PA levels increased a participant’s odds of having a healthy CRF level, by 48% and 40%, respectively. Although the mechanisms via which CRF may be influenced by dietary habits remain unclear, health policy-makers should consider opportunities for improving both CRF and dietary habits.