Background Childhood anemia is a global public health issue. In this study, we assessed the potential sociodemographic and dietary factors associated with the prevalence of anemia among children aged 6–59 months in Nigeria. Methods In this cross-sectional study, we collected dietary information and demographic data on 6,338 children with anemia from the Nigerian Demographic and Health Surveys (2018). The association between the occurrence of anemia and the demographic and dietary factors was determined by conducting Chi-squared tests. Additionally, bivariate and multivariate order logit models were constructed and reported as odds ratios. Results The results of the multivariate analysis showed that the risk of anemia was reduced by 13% and 44% in children aged 13–36 months (OR = 0.87; 95% CI = 0.77–0.98; p = 0.019) and 37–59 months (OR = 0.56; 95% CI = 0.49–0.63; p < 0.001), respectively, compared to the risk of anemia in children aged 6–12 months. Anemia was 28% less likely in children of non-anemic mothers (OR = 0.72; 95% CI = 0.66–0.80; p < 0.001) than children of anemic mothers. Children fed pumpkin, carrot, squash, and sweet potato showed a lower occurrence of anemia by 17% (OR = 0.83; 95% CI = 0.70–0.99; p = 0.036) compared to those who were not fed these vegetables. Chances of anemia increased by 14% in children who were fed white potatoes, white yams, manioc, cassava, and other root-based foods (OR = 1.14; 95% CI = 1.01–1.29; p = 0.036). Conclusion This study highlighted the impact of a plant-based diet on the high prevalence of childhood anemia in Nigeria. Therefore, reformation of dietary habits, the inclusion of nutritional supplements, and food-fortification programs with reductions in maternal anemia are recommended.