Firefighting is associated with high-level physical demands and requires appropriate physical fitness. Considering that obesity has been correlated with decreased cardiorespiratory fitness (CRF) and that the prevalence of obesity may also be elevated within firefighters (FF), we analyzed the association between CRF and body composition (BC) in Brazilian military FF. We assessed 4,237 male FF (18-49 years) who performed a physical fitness test that included BC and CRF. Body composition was assessed by body mass index (BMI), body adiposity index (BAI), body fat percentage (BF%), and waist circumference (WC). CRF was assessed by the 12-minute Cooper test. Comparisons of VO2max between the BC categories were analyzed using the Mann-Whitney test, and the analysis was adjusted for age using the General Linear Model. The Spearman test was used for correlation analysis and the odds ratio (OR) was calculated to assess the odds of the unfit group (≤ 12 metabolic equivalents [METs]) for poor BC. Statistically significant differences were considered when p ≤ 0.05. Considering the BMI categories, 8 volunteers (0.2%) were underweight, 1,306 (30.8%) were normal weight, 2,301 (54.3%) were overweight, and 622 (14.7%) were obese. The VO2max was negatively correlated with age (rs = -0.21), BMI (rs = -0.45), WC (rs = -0.50), and BAI (rs = -0.35) (p < 0.001). Cardiorespiratory fitness was lower in the obese compared with the nonobese for all age categories (-3.8 ml · kg(-1) · min(-1); p < 0.001) and for all BC indices (-4.5 ml · kg(-1) · min(-1); p < 0.001). The OR of the unfit group having poor BC in all indices varied from 2.9 to 8.1 (p < 0.001). Despite the metabolically healthy obesity phenomenon, we found a strong association between CRF and BC irrespective of age and the BC method (BMI, BAI, WC, or BF%). These findings may aid in improving FF training programs with a focus on health and performance.