Objectives Household air pollution (HAP) is one of the leading causes of respiratory illness and deaths among young children in low and lower-middle income countries. This study examines for the first time trends in the association between HAP from cooking fuel and under-five mortality and measures the potential impact of interventions to reduce HAP using Nepal Demographic and Health Survey datasets (2001–2011). Methods A total of 17,780 living children across four age-groups (neonatal 0–28 days, post-neonatal 1–11 months, child 12–59 months and under-five 0–59 months) were included and multi-level logistic regression models were used for analyses. Population attributable fractions of key risk factors and potential impact fractions assessing the impact of previous interventions to reduce exposure prevalence were also calculated. Results Use of cooking fuel was associated with total under-five mortality (OR 2.19, 95% CI 1.37–3.51, P = 0.001) in Nepal, with stronger associations evident for sub-group analyses of neonatal mortality (OR 2.67, 95% CI 1.47–4.82, P = 0.001).