Background: Child undernutrition and flooding are highly prevalent public health issues in Asia, yet epidemiological studies investigating this association are lacking. Methods: To investigate to what extent floods exacerbate poor nutritional status in children and identify most vulnerable groups, we conducted a population-based survey of children aged 6–59 months inhabiting flooded and non-flooded communities of the Jagatsinghpur district, Odisha (India), one year after large floods in 2008. Anthropometric measurements on 879 children and child, parental and household level variables were collected through face-to-face interviews in September 2009. The association between flooding and the prevalence of wasting, stunting and underweight was examined using weighted multivariate logistic regression for children inhabiting communities exposed solely to floods in 2008 and those communities repeatedly flooded (2006 and 2008) controlling for parental education and other relevant variables. We examined the influence of age on this association. Propensity score matching was conducted to test the robustness of our findings. Results: The prevalence of wasting among children flooded in 2006 and 2008 was 51.6%, 41.4% in those flooded only in 2008, and 21.2% in children inhabiting non-flooded communities. Adjusting by confounders, the increased prevalence relative to non-flooded children in the exposed groups were 2.30 (adjusted prevalence ratio (aPR); 95% CI: 1.86, 2.85) and 1.94 (95% CI: 1.43, 2.63), respectively. Among repeatedly flooded communities, cases of severe wasting in children were 3.37 times more prevalent than for children inhabiting in those non-flooded (95% CI: 2.34, 4.86) and nearly twice more prevalent relative to those flooded only once. Those children younger than one year during previous floods in 2006 showed the largest difference in prevalence of wasting compared to their non-flooded counterparts (aPR: 4.01; 95% CI: 1.51, 10.63). Results were robust to alternative adjusted models and in propensity score matching analyses. For similar analyses, no significant associations were found for child stunting, and more moderate effects were observed in the case of child underweight. Conclusions: Particularly in low-resource or subsistence-farming rural settings, long-lasting nutritional response in the aftermath of floods should be seriously considered to counteract the long-term nutritional effects on children, particularly infants, and include their mothers on whom they are dependent. The systematic monitoring of nutritional status in these groups might help to tailor efficient responses in each particular context.