BACKGROUND: Verbal autopsy is currently the only option for obtaining cause of death information in most populations with a widespread HIV/AIDS epidemic. METHODS: With the use of a data-driven algorithm, a set of criteria for classifying AIDS mortality was trained. Data from two longitudinal community studies in Tanzania and Zimbabwe were used, both of which have collected information on the HIV status of the population over a prolonged period and maintained a demographic surveillance system that collects information on cause of death through verbal autopsy. The algorithm was then tested in different times (two phases of the Zimbabwe study) and different places (Tanzania and Zimbabwe). RESULTS: The trained algorithm, including nine signs and symptoms, performed consistently based on sensitivity and specificity on verbal autopsy data for deaths in 15-44-year-olds from Zimbabwe phase I (sensitivity 79%; specificity 79%), phase II (sensitivity 83%; specificity 75%) and Tanzania (sensitivity 75%; specificity 74%) studies. The sensitivity dropped markedly for classifying deaths in 45-59-year-olds. CONCLUSIONS: Verbal autopsy can consistently measure AIDS mortality with a set of nine criteria. Surveillance should focus on deaths that occur in the 15-44-year age group for which the method performs reliably. Addition of a handful of questions related to opportunistic infections would enable other widely used verbal autopsy tools to apply this validated method in areas for which HIV testing and hospital records are unavailable or incomplete.