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