Malnutrition rates among children 0-36 months and women of reproductive age in Nigeria are high and vary significantly across rural-urban locations, geopolitical regions, and agroecological zones, constituting a significant public health challenge. Using National Demographic Health Survey (NDHS) 2003 data, we sought to understand better what the determinants of child and maternal nutrition are and whether they differ significantly in terms of their nature, levels, and effects across these domains. We also sought to understand what implications any significant differences would have for policy responses. A range of socioeconomic, demographic, and public health related factors work together to influence maternal and child nutrition outcomes among rural and urban dwellers across the geopolitical regions and agroecological zones. Our analyses show some major variables that influence maternal and child nutrition including household economic status, having a household head predominantly engaged with agriculture, maternal work to earn income, and maternal education or knowledge. Other determinants include mother’s age, decision-making on her income and her health, percent of children under five years in a household, child based characteristics such as age and sex, dietary diversity and meal frequency, and public health services such as having antenatal care and vaccinations. The results indicate that while the effect of some determinants cuts across many of the rural and urban regions and zones, the effects of other determinants are more localized in rural or urban settings of particular regions and zones. While maternal education and knowledge are critical for improved maternal and child nutrition, efforts to improve household economic status, increase the rural farmers’ benefits from agriculture, and empower mothers to earn income and take decisions, complemented with nutritional and public health services, are more likely to improve both child and maternal nutrition in the rural areas than in urban, especially in regions with the highest burden of malnutrition. Current levels of determinants appear linked more to policy implementation challenges than to the lack of or deficient components of policies to effectively address these determinants. To substantially improve nutrition conditions of mothers and children in rural Nigeria, strengthening or reviewing current policy and implementation processes in key areas is critical.