Anemia is an increasingly recognized problem in sub-Saharan Africa. To determine the magnitude, severity, and associated factors of anemia among hospitalized children aged 6-59 months, HIV-infected and HIV-exposed uninfected children (a child born to a known HIV-infected mother) with a documented fever or history of fever within the prior 24 hours of hospital admission (N = 413) were included in this analysis. Of 413 children enrolled, 364 (88%) were anemic, with 53% classified as mild anemia (hemoglobin [Hb] 7-9.9 g/dL). The most common diagnoses associated with hospital admission included acute respiratory illness (51%), malnutrition (47%), gastroenteritis/diarrhea (25%), malaria (17%), and bacteremia (13%). A diagnosis of malaria was associated with a decrease in Hb by 1.54 g/dL (P < 0.001). In HIV-infected patients, malaria was associated with a similar decrease in Hb (1.47 g/dL), whereas a dual diagnosis of bacteremia and malaria was associated with a decrease in Hb of 4.12 g/dL (P < 0.001). No difference was seen in Hb for patients on antiretroviral therapy versus those who were not. A diagnosis of bacteremia had a roughly 4-fold increased relative odds of death during hospitalization (adjusted odds ratio = 3.97; 95% CI: 1.61, 9.78; P = 0.003). The etiology of anemia in high-burden malaria, HIV, tuberculosis, and poor nutrition countries is multifactorial, and multiple etiologies may be contributing to one's anemia at any given time. Algorithms used by physician and nonphysician clinicians in Mozambique should incorporate integrated and non-disease specific approaches to pediatric anemia management and should include improved access to blood culture.