A prospective cohort study measured mortality during nutritional rehabilitation among HIV-infected and uninfected children, aged 6-59 months, with severe acute malnutrition (SAM). Children were tested for HIV and CD4% on admission to the nutrition rehabilitation unit (NRU). Mortality was assessed by following children to 4 months post discharge from the NRU or death if earlier. Overall mortality was 14.8% (67/454) and HIV prevalence was 17.4% (79/454). HIV-infected children were significantly more likely to die than uninfected children [35.4% (28/79) vs. 10.4% (39/375), P<0.001], and 85.7% of deaths occurred in children with a CD4% less than 20. Forty percent (18/45) of HIV-infected children with a CD4% <20 died, in contrast to 15% (3/20) of HIV-infected children with a CD4% >20 (P=0.05). Routine testing and treatment for HIV among all malnourished children is necessary to improve quality of care and reduce mortality among children with SAM.