Background Children living in sub-Saharan Africa have a high burden of rickets and infectious diseases, conditions that are linked to vitamin D deficiency. However, data on the vitamin D status of young African children and its environmental and genetic predictors are limited. We aimed to examine the prevalence and predictors of vitamin D deficiency in young African children. Methods We measured 25-hydroxyvitamin D (25(OH)D) and typed the single nucleotide polymorphisms, rs4588 and rs7041, in the GC gene encoding the vitamin D binding protein (DBP) in 4509 children aged 0–8 years living in Kenya, Uganda, Burkina Faso, The Gambia and South Africa. We evaluated associations between vitamin D status and country, age, sex, season, anthropometric indices, inflammation, malaria and DBP haplotypes in regression analyses. Results Median age was 23.9 months (interquartile range [IQR] 12.3, 35.9). Prevalence of vitamin D deficiency using 25(OH)D cut-offs of < 30 nmol/L and < 50 nmol/L was 0.6% (95% CI 0.4, 0.9) and 7.8% (95% CI 7.0, 8.5), respectively. Overall median 25(OH)D level was 77.6 nmol/L (IQR 63.6, 94.2). 25(OH)D levels were lower in South Africa, in older children, during winter or the long rains, and in those with afebrile malaria, and higher in children with inflammation. 25(OH)D levels did not vary by stunting, wasting or underweight in adjusted regression models. The distribution of Gc variants was Gc1f 83.3%, Gc1s 8.5% and Gc2 8.2% overall and varied by country. Individuals carrying the Gc2 variant had lower median 25(OH)D levels (72.4 nmol/L (IQR 59.4, 86.5) than those carrying the Gc1f (77.3 nmol/L (IQR 63.5, 92.8)) or Gc1s (78.9 nmol/L (IQR 63.8, 95.5)) variants. Conclusions Approximately 0.6% and 7.8% of young African children were vitamin D deficient as defined by 25(OH)D levels < 30 nmol/L and < 50 nmol/L, respectively. Latitude, age, season, and prevalence of inflammation and malaria should be considered in strategies to assess and manage vitamin D deficiency in young children living in Africa.