Background Millions of people in low and low middle income countries suffer from extreme hunger and malnutrition. Research on the effect of food insecurity on child nutrition is concentrated in high income settings and has produced mixed results. Moreover, the existing evidence on food security and nutrition in children in low and middle income countries is either cross-sectional and/or is based primarily on rural populations. In this paper, we examine the effect of household food security status and its interaction with household wealth status on stunting among children aged between 6 and 23 months in resource-poor urban setting in Kenya. Methods We use longitudinal data collected between 2006 and 2012 from two informal settlements in Nairobi, Kenya. Mothers and their new-borns were recruited into the study at birth and followed prospectively. The analytical sample comprised 6858 children from 6552 households. Household food security was measured as a latent variable derived from a set of questions capturing the main domains of access, availability and affordability. A composite measure of wealth was calculated using asset ownership and amenities. Nutritional status was measured using Height-for-Age (HFA) z-scores. Children whose HFA z-scores were below −2 standard deviation were categorized as stunted. We used Cox regression to analyse the data. Results The prevalence of stunting was 49 %. The risk of stunting increased by 12 % among children from food insecure households. When the joint effect of food security and wealth status was assessed, the risk of stunting increased significantly by 19 and 22 % among children from moderately food insecure and severely food insecure households and ranked in the middle poor wealth status. Among the poorest and least poor households, food security was not statistically associated with stunting. Conclusion Our results shed light on the joint effect of food security and wealth status on stunting. Study findings underscore the need for social protection policies to reduce the high rates of child malnutrition in the urban informal settlements.