In low-income countries, undernutrition and infections play a major role in childhood anemia. Stunted children may be at particular risk of anemia. In a cross-sectional study nested in a nutrition trial among 12–59-month-old stunted children in eastern Uganda, we measured hemoglobin (Hb) and markers of iron, cobalamin, folate and vitamin A status. We assessed low micronutrient status, socio-demography, stunting severity, inflammation and malaria as correlates of Hb and anemia using linear and logistic regression analyses, respectively. Of 750 stunted children, the mean ± SD age was 32.0 ± 11.7 months and 55% (n = 412) were male. The mean Hb was 104 ± 15 g/L and 65% had anemia, Hb < 110 g/L. In a multivariable model with age, sex and inflammation, the following were associated with lower Hb: serum ferritin < 12 µg/L (−5.6 g/L, 95% CI: −8.6; −2.6), transferrin receptors > 8.3 mg/L (−6.2 g/L, 95% CI: −8.4; −4.0), plasma folate <20 nmol/L (−4.6 g/L, 95% CI: −8.1;−1.1), cobalamin < 222 pmol/L (−3.0 g/L, 95% CI: −5.4; −0.7) and serum retinol-binding protein < 0.7 µmol/L (−2.0 g/L, 95% CI: −4.1; 0.2). In addition, severe stunting, inflammation and malaria were negative correlates. Anemia is common among stunted children in eastern Uganda; micronutrient deficiencies, inflammation and malaria are associated with low Hb.