Vitamin D regulates the master iron hormone hepcidin, and iron in turn alters vitamin D metabolism. Although vitamin D and iron deficiency are highly prevalent globally, little is known about their interactions in Africa. To evaluate associations between vitamin D and iron status we measured markers of iron status, inflammation, malaria parasitemia, and 25-hydroxyvitamin D (25(OH)D) concentrations in 4509 children aged 0.3 months to 8 years living in Kenya, Uganda, Burkina Faso, The Gambia, and South Africa. Prevalence of iron deficiency was 35.1%, and prevalence of vitamin D deficiency was 0.6% and 7.8% as defined by 25(OH)D concentrations of <30 nmol/L and <50 nmol/L, respectively. Children with 25(OH)D concentrations of <50 nmol/L had a 98% increased risk of iron deficiency (OR 1.98 [95% CI 1.52, 2.58]) compared to those with 25(OH)D concentrations >75 nmol/L. 25(OH)D concentrations variably influenced individual markers of iron status. Inflammation interacted with 25(OH)D concentrations to predict ferritin levels. The link between vitamin D and iron status should be considered in strategies to manage these nutrient deficiencies in African children.