Micronutrient deficiencies and stunting are prevalent. We assessed correlates of iron, cobalamin, folate, and vitamin A biomarkers in a cross-sectional study of stunted children aged 12–59 months in eastern Uganda. The biomarkers measured were serum ferritin (S-FE), soluble transferrin receptor (S-TfR), retinol binding protein (S-RBP), plasma cobalamin (P-Cob), methylmalonic acid (P-MMA), and folate (P-Fol). Using linear regression, we assessed socio-demography, stunting severity, malaria rapid test, and inflammation as correlates of micronutrient biomarkers. Of the 750 children, the mean (SD) age was 32.0 (11.7) months, and 45% were girls. Iron stores were depleted (inflammation-corrected S-FE < 12 µg/L) in 43%, and 62% had tissue iron deficiency (S-TfR > 8.3 mg/L). P-Cob was low (<148 pmol/L) and marginal (148–221 pmol/L) in 3% and 20%, and 16% had high P-MMA (>0.75 µmol/L). Inflammation-corrected S-RBP was low (<0.7 µmol/L) in 21% and P-Fol (<14 nmol/L) in 1%. Age 24–59 months was associated with higher S-FE and P-Fol and lower S-TfR. Breastfeeding beyond infancy was associated with lower iron status and cobalamin status, and malaria was associated with lower cobalamin status and tissue iron deficiency (higher S-TfR) despite iron sequestration in stores (higher S-FE). In conclusion, stunted children have iron, cobalamin, and vitamin A deficiencies. Interventions addressing stunting should target co-existing micronutrient deficiencies.