OBJECTIVE: To present an algorithm for primary-care health workers for identifying HIV-infected adolescents in populations at high risk through mother-to-child transmission. METHODS: Five hundred and six adolescent (10-18 years) attendees to two primary care clinics in Harare, Zimbabwe, were recruited. A randomly extracted 'training' data set (n = 251) was used to generate an algorithm using variables identified as associated with HIV through multivariable logistic regression. Performance characteristics of the algorithm were evaluated in the remaining ('test') records (n = 255) at different HIV prevalence rates. RESULTS: HIV prevalence was 17%, and infection was independently associated with client-reported orphanhood, past hospitalization, skin problems, presenting with sexually transmitted infection and poor functional ability. Classifying adolescents as requiring HIV testing if they reported >1 of these five criteria had 74% sensitivity and 80% specificity for HIV, with the algorithm correctly predicting the HIV status of 79% of participants. In low-HIV-prevalence settings (<2%), the algorithm would have a high negative predictive value (≥ 99.5%) and result in an estimated 60% decrease in the number of people needing to test to identify one HIV-infected individual, compared with universal testing. CONCLUSIONS: Our simple algorithm can identify which individuals are likely to be HIV infected with sufficient accuracy to provide a screening tool for use in settings not already implementing universal testing policies among this age-group, for example immigrants to low-HIV-prevalence countries.