Iron deficiency (ID) and human immunodeficiency virus (HIV) infection frequently coexist. Little data exist on ID in HIV-infected individuals, partly because the iron marker ferritin is altered by inflammation common in HIV infection. We measured iron biomarkers (ferritin, soluble transferrin receptor [sTfR], hepcidin) and red cell indices (hemoglobin, mean corpuscular volume [MCV]) in newly diagnosed, antiretroviral therapy-naive, HIV-infected (N = 138) and uninfected (N = 52) Kenyan adults enrolled in a study of the immune response to malaria. We compared markers between infected and uninfected groups with t test and Wilcoxon Rank-Sum, used Spearman correlation to determine the association between iron and inflammatory markers, and applied logistic regression to determine which markers best predicted anemia. HIV-infected individuals had lower hemoglobin (P < 0.001), lower MCV (P < 0.001), higher sTfR (P = 0.003), and a greater prevalence of ID (sTfR > 8.3 mg/L) than uninfected individuals. Ferritin was elevated in HIV-infected individuals and was more strongly correlated with C-reactive protein (ρ = 0.43, P < 0.001) and hepcidin (ρ = 0.69, P < 0.001) than with hemoglobin. The best predictor of anemia in HIV-infected participants was sTfR, with a one log-unit increase in sTfR associated with a 6-fold increase in the odds of anemia (odds ratio = 6.3, 95% confidence interval: 1.8-21.8). These data suggest a significant burden of ID among treatment-naive HIV-infected Kenyan adults. Soluble transferrin receptor may be a reliable marker of ID in HIV-mediated inflammation.