Child labor in developing countries continues to be a topic of policy and academic concern, particularly in Africa where there are more working children than in any other region. Scholarly attention has been drawn in part to gender, place of residence, and socioeconomic status as factors that shape the type of work that children perform and whether it impacts educational attainment. I explore these issues in the context of Nigeria through analysis of data from the 2004 Nigeria Demographic and Health Survey EdData Survey. A series of logistic regression models of child labor confirm the existence of gender and, especially, socioeconomic disparities in children’s work. The data also indicate that girls and rural children face a double risk of working if they belong to poor households. A policy implication is that poverty alleviation programs—such as Mexico’s Oportunidades program (the erstwhile PROGRESA)—may help to reduce those forms of child labor that interfere with schooling. That this program has been found to more beneficial for girls suggests it may be particularly appropriate for Nigeria where gender disparities persist.