Introduction: Several studies from resource-limited settings have demonstrated that clinical and immunologic criteria are poor predictors of virologic failure, confirming the need for viral load monitoring or at least an algorithm to target viral load testing. We used data from an electronic patient management system to develop an algorithm to identify patients at risk of viral failure using a combination of accessible and inexpensive markers. Methods: We analyzed data from HIV-positive adults initiated on antiretroviral therapy (ART) in Johannesburg, South Africa, between April 2004 and February 2010. Viral failure was defined as ≥2 consecutive HIV-RNA viral loads >400 copies/ml following suppression ≤400 copies/ml. We used Cox-proportional hazards models to calculate hazard ratios (HR) and 95% confidence intervals (CI). Weights for each predictor associated with virologic failure were created as the sum of the natural logarithm of the adjusted HR and dichotomized with the optimal cut-off at the point with the highest sensitivity and specificity (i.e. ≤4 vs. >4). We assessed the diagnostic accuracy of predictor scores cut-offs, with and without CD4 criteria (CD4 <100 cells/mm3; CD4 < baseline; >30% drop in CD4), by calculating the proportion with the outcome and the observed sensitivity, specificity, positive and negative predictive value of the predictor score compared to the gold standard of virologic failure. Results: We matched 919 patients with virologic failure (1:3) to 2756 patients without. Our predictor score included variables at ART initiation (i.e. gender, age, CD4 count <100 cells/mm3, WHO stage III/IV and albumin) and laboratory and clinical follow-up data (drop in haemoglobin, mean cell volume (MCV) <100 fl, CD4 count <200 cells/mm3, new or recurrent WHO stage III/IV condition, diagnosis of new condition or symptom and regimen change). Overall, 51.4% had a score 51.4% had a score ≥4 and 48.6% had a score <4. A predictor score including CD4 criteria performed better than a score without CD4 criteria and better than WHO clinico-immunological criteria or WHO clinical staging to predict virologic failure (sensitivity 57.1% vs. 40.9%, 25.2% and 20.9%, respectively). Conclusions: Predictor scores or risk categories, with CD4 criteria, could be used to identify patients at risk of virologic failure in resource-limited settings so that these patients may be targeted for focused interventions to improve HIV treatment outcomes.