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.