This study assessed the trend in the level of under-five stunting across the different dimensions of the intersection of household wealth status (rich, average, or poor), type of place of residence (rural or urban), and gender of household heads (male or female) to identify households that were persistently most at risk of under-five stunting in Nigeria. A secondary data analysis was conducted on nationally representative children’s data from four consecutive national surveys (Nigeria Demographic and Health Survey) conducted in 2003, 2008, 2013, and 2018 in Nigeria. The study outcome variable was under-five stunting status (stunted and “not stunted”). The primary independent variable was household type derived from the intersection of the gender of the household head, household wealth status, and type of place of residence. Meta-analyses with forest plots were used to determine log odds ratios of stunting in different household types using Rich Female-Headed Urban (RFHU) Households as the reference category. Multivariate analysis was also conducted using a Generalized Linear Model for each year’s dataset. The meta-analyses show that the odds of a child becoming stunted were significantly 4.26 times higher in PMHR, 3.25 times higher in PFHR, 2.92 times higher in PMHU, 2.59 times higher in AMHR, and 2.48 times higher in AMHU households compared to RFHU households. The multivariate models also show that from 2003, 2008, 2013–2018, PMHR (AOR: 5.12; 3.31; 4.22; & 3.72; p < 0.05), PMHU (AOR: 3.25; 2.75; 2.60; & 2.84; p < 0.05), PFHR (AOR: 3.58; 2.86; 3.47; & 3.07; p < 0.05), AMHU (AOR: 3.96; 2.47; 2.25; & 1.97; p < 0.05), and AMHR (AOR: 4.47; 2.31; 2.37; & 2.08; p < 0.05), consistently had significantly higher odds of predisposing under-five children to stunting than RFHU households. These findings offer fresh insights to guide policymakers in developing new policies and help program managers design and implement more tailored nutrition-sensitive interventions and programs for the households most at risk of under-five stunting in Nigeria.