BACKGROUND: In sub-Saharan Africa, malnutrition and malaria remain major causes of morbidity and mortality in young children. There are conflicting data as to whether malnutrition is associated with an increased or decreased risk of malaria. In addition, data are limited on the potential interaction between HIV infection and the association between malnutrition and the risk of malaria. METHODS: A cohort of 100 HIV-unexposed, 203 HIV-exposed (HIV negative children born to HIV-infected mothers) and 48 HIV-infected children aged 6 weeks to 1 year were recruited from an area of high malaria transmission intensity in rural Uganda and followed until the age of 2.5 years. All children were provided with insecticide-treated bed nets at enrolment and daily trimethoprim-sulphamethoxazole prophylaxis (TS) was prescribed for HIV-exposed breastfeeding and HIV-infected children. Monthly routine assessments, including measurement of height and weight, were conducted at the study clinic. Nutritional outcomes including stunting (low height-for-age) and underweight (low weight-for-age), classified as mild (mean z-scores between -1 and -2 during follow-up) and moderate-severe (mean z-scores < -2 during follow-up) were considered. Malaria was diagnosed when a child presented with fever and a positive blood smear. The incidence of malaria was compared using negative binomial regression controlling for potential confounders with measures of association expressed as an incidence rate ratio (IRR). RESULTS: The overall incidence of malaria was 3.64 cases per person year. Mild stunting (IRR = 1.24, 95% CI 1.06-1.46, p = 0.008) and moderate-severe stunting (IRR = 1.24, 95% CI 1.03-1.48, p = 0.02) were associated with a similarly increased incidence of malaria compared to non-stunted children. Being mildly underweight (IRR = 1.09, 95% CI 0.95-1.25, p = 0.24) and moderate-severe underweight (IRR = 1.12, 95% CI 0.86-1.46, p = 0.39) were not associated with a significant difference in the incidence of malaria compared to children who were not underweight. There were no significant interactions between HIV-infected, HIV-exposed children taking TS and the associations between malnutrition and the incidence of malaria. CONCLUSIONS: Stunting, indicative of chronic malnutrition, was associated with an increased incidence of malaria among a cohort of HIV-infected and -uninfected young children living in an area of high malaria transmission intensity. However, caution should be made when making causal inferences given the observational study design and inability to disentangle the temporal relationship between malnutrition and the incidence of malaria. TRIAL REGISTRATION: ClinicalTrials.gov: NCT00527800.