INTRODUCTION: Given the high prevalence of malnutrition in a malaria-endemic setting, improving nutritional status could serve as a tool to prevent malaria. However, the relationship between the two conditions remains unclear. Therefore, this study assessed the association between under-nutrition and malaria among a cohort of children aged 6 to 59 months old. METHODS: Two cohorts of children were followed for 89 weeks in a rural Rift Valley area of Ethiopia. In the first approach (malaria-malnutrition), a cohort of 2,330 non-stunted and 4,204 non-wasted children were included to assess under-nutrition (outcome) based on their previous malaria status (exposure). In the second approach (malnutrition-malaria), a cohort of 4,468 children were followed-up to measure malaria (outcome), taking under-nutrition as an exposure. A weekly home visit was carried out to identify malaria cases. Four anthropometry surveys were conducted, and generalized estimating equation (GEE) method was used to measure the association between undernutrition and malaria. RESULTS: The prevalence of stunting was 44.9% in December 2014, 51.5% in August 2015, 50.7% in December 2015 and 48.1% in August 2016. We observed 103 cases with 118 episodes of malaria, 684 new stunting and 239 new wasting cases. The incidence rate per 10,000 weeks of observation was 3.8 for malaria, 50.4 for stunting and 8.2 for wasting. Children with malaria infection, [Adjusted Odds Ratio (AOR) = 1.9; 95% Confidence Interval (CI), 1.2-2.9)] and younger age (AOR = 1.3; 95% CI, 1.1-1.5) were more likely to be stunted. Furthermore, children with malaria infection (AOR = 8.5; 95% CI, 5.0-14.5) and young age group (AOR = 1.6; 95% CI, 1.2-2.1) were more likely to be wasted. However, stunting and wasting were not risk factors of subsequent malaria illness. CONCLUSIONS: Malaria infection was a risk factor for stunting and wasting, but stunting or wasting was not associated with subsequent malaria illness. As our study shows that malaria is a risk factor for stunting and wasting, a close follow-up of the nutritional status of such children may be needed. TRIAL REGISTRATION: PACT R2014 11000 882128 (8 September 2014).