There is a lack of studies that analyze the association between micronutrient-related biomarker status and physical fitness in adolescents. In the present study, biochemical parameters for iron and vitamin status were studied, along with objective measures of physical fitness in healthy male and female European adolescents. One thousand eighty-nine adolescents (580 girls, 12.5–17.5 yr) from the Healthy Lifestyle in Europe by Nutrition in Adolescence (HELENA) cross-sectional study were included. Hierarchical linear models were performed to determine the associations between micronutrient biomarkers and physical fitness. Age, seasonality, latitude, body mass index, menarche (in girls), and physical activity were used as covariates. For cardiorespiratory fitness, concentrations of hemoglobin, retinol, and vitamin C in male adolescents and β-carotene and 25(OH)D in female adolescents were associated with maximal oxygen consumption. For muscular fitness, concentrations of hemoglobin, β-carotene, retinol, and α-tocopherol in male adolescents and β-carotene and 25(OH)D in female adolescents were associated with better performance of the standing long jump test. In summary, concentrations of hemoglobin and most antioxidant vitamins in male adolescents and β-carotene and 25(OH)D in female adolescents were positively associated with cardiorespiratory and muscular fitness, after controlling for relevant confounders. The associations between physical fitness and iron or vitamin status observed in this cross-sectional study in adolescents should be followed up by a study specifically designed to evaluate causal relationships.