In resource-limited settings where viral load (VL) monitoring is scarce or unavailable, clinicians must use immunological and clinical criteria to define HIV virological treatment failure. This study examined the performance of World Health Organization (WHO) clinical and immunological failure criteria in predicting virological failure in HIV patients receiving antiretroviral therapy (ART). In a HIV/AIDS program in Busia District Hospital, Kenya, a retrospective, cross-sectional cohort analysis was performed in April 2008 for all adult patients (>18 years old) on ART for ≥12 months, treatment-naive at ART start, attending the clinic at least once in last 6 months, and who had given informed consent. Treatment failure was assessed per WHO clinical (disease stage 3 or 4) and immunological (CD4 cell count) criteria, and compared with virological failure (VL >5,000 copies/mL). Of 926 patients, 123 (13.3%) had clinically defined treatment failure, 53 (5.7%) immunologically defined failure, and 55 (6.0%) virological failure. Sensitivity, specificity, positive predictive value, and negative predictive value of both clinical and immunological criteria (combined) in predicting virological failure were 36.4%, 83.5%, 12.3%, and 95.4%, respectively. In this analysis, clinical and immunological criteria were found to perform relatively poorly in predicting virological failure of ART. VL monitoring and new algorithms for assessing clinical or immunological treatment failure, as well as improved adherence strategies, are required in ART programs in resource-limited settings.