Objectives This study aims to improve the understanding of the relationship between exposure to floods and malnutrition in children aged 6-59 months in rural India. Research has focused exclusively on Bangladeshi children, and few controlled epidemiological studies are available. Method A community-based cross-sectional study of child nutritional status was carried out in 14 flooded and 18 non-flooded villages of Jagatsinghpur district (Orissa) within one month of the September 2008 floods, and similarly affected by flooding in August 2006. Face-to-face interviews were conducted in 757 households in the flooded villages and 816 in the non-flooded communities. Data used in this study were from those households with children aged 6-59 months. In total, 191 and 161 children were measured, respectively. The association between various malnutrition indicators and the exposure to floods was assessed by univariate and multivariate logistic regression. Results Adjusted analyses revealed that children in flooded households were more likely stunted compared with those in non-flooded ones (adjusted prevalence ratio 1.60; 95% CI 1.05 to 2.44). The prevalence of underweight was also higher in children living in the flooded communities (adjusted prevalence ratio 1.86; 95% CI 1.04 to 3.30). Further analyses found that the 26-36-month flooded cohort, thus those children younger than 1 year during the precedent flood in August 2006, attained the largest difference in levels of stunting compared with the unexposed group of the same age. Conclusion Exposure to floods is associated with long-term malnutrition in these rural communities of Orissa, India. Children exposed to floods during their first year of life presented higher levels of chronic malnutrition. Long-term malnutrition prevention programmes after floods should be implemented in flood-prone areas.