Background Malnutrition accounts for 45% of mortality in children under five years old, despite a global mobilization against chronic malnutrition. In Madagascar, the most recent data show that the prevalence of stunting in children under five years old is still around 47.4%. This study aimed to identify the determinants of stunting in children in rural areas of Moramanga and Morondava districts to target the main areas for intervention. Methods A case-control study was conducted in children aged from 6 to 59.9 months, in 2014–2015. We measured the height and weight of mothers and children and collected data on child, mother and household characteristics. One stool specimen was collected from each child for intestinal parasite identification. We used a multivariate logistic regression model to identify the determinants of stunting using backwards stepwise methods. Results We included 894 and 932 children in Moramanga and in Morondava respectively. Stunting was highly prevalent in both areas, being 52.8% and 40.0% for Moramanga and Morondava, respectively. Stunting was most associated with a specific age period (12mo to 35mo) in the two study sites. Infection with Trichuris trichiura (aOR: 2.4, 95% CI: 1.1–5.3) and those belonging to poorer households (aOR: 2.3, 95% CI: 1.6–3.4) were the major risk factors in Moramanga. In Morondava, children whose mother had activities outside the household (aOR: 1.7, 95% CI: 1.2–2.5) and those perceived to be small at birth (aOR: 1.6, 95% CI: 1.1–2.1) were more likely to be stunted, whereas adequate birth spacing (≥24months) appeared protective (aOR: 0.4, 95% CI: 0.3–0.7). Conclusion Interventions that could improve children’s growth in these two areas include poverty reduction, women’s empowerment, public health programmes focusing on WASH and increasing acceptability, and increased coverage and quality of child/maternal health services.