Observations in Nigeria have indicated polio vaccination refusal related to religion that ultimately affected child morbidity and mortality. This study assessed the role of religion in under-five (0–59 months) mortality using a cross-sectional, nationally representative sample of 7,620 women aged 15–49 years from the 2003 Nigeria Demographic and Health Survey and included 6,029 children. Results show that mother’s affiliation to Traditional indigenous religion is significantly associated with increased under-five mortality. Multivariable modelling demonstrated that this association is explained by differential use of maternal and child health services, specifically attendance to prenatal care. To reduce child health inequity, these results need to be incorporated in the formulation of child health policies geared towards achieving a high degree of attendance to prenatal care, irrespective of religious affiliation.