Clinical criteria are recommended to select HIV-infected patients for initiation of antiretroviral therapy when CD4 lymphocyte testing is unavailable. We evaluated the performance characteristics of WHO staging criteria, anthropometrics, and simple laboratory measurements for predicting CD4 lymphocyte count (CD4 count) <200 cells/mm3 among HIV-infected patients in Tanzania. A total of 202 adults, diagnosed with HIV infection through community-based testing, underwent a detailed evaluation including staging history and examination, anthropometry, complete blood count, erythrocyte sedimentation rate (ESR), and CD4 count. Univariable analysis and recursive partitioning were used to identify characteristics associated with CD4 count <200 cells/mm3. Of 202 participants 109 (54%) had a CD4 count <200 cells/mm3. Characteristics most strongly associated with CD4 count <200 cells/mm3 (p-value <0.0001) were the presence of mucocutaneous manifestations (72% vs. 28%), lower total lymphocyte count (TLC) (median 1450 vs. 2200 cells/mm3), lower total white blood cell count (median 4200 vs. 5500 cells/mm3), and higher ESR (median 95 vs. 53 mm/h). In a partition tree model, TLC <1200 cells/mm3, ESR ≥120 mm/h, or the presence of mucocutaneous manifestations yielded a sensitivity of 0.85 and specificity of 0.63 for predicting CD4 count <200 cells/mm3. The sensitivity of the 2006 WHO Staging system improved from 0.75 to 0.93 with inclusion of these parameters, at the expense of specificity (0.36 to 0.26). The presence of mucocutaneous manifestations, TLC <1200 cells/mm3, or ESR ≥120 mm/h was a strong predictor of CD4 count <200 cells/mm3 and enhanced the sensitivity of the 2006 WHO staging criteria for identifying patients likely to benefit from antiretrovirals.