It seems natural to ask "what worked" when looking at nations achieving HIV prevalence declines. Yet this seemingly benign question is fraught with complexity and often poorly understood. This article presents a framework to comprehend the areas in which evidence is needed to assess the policy causes of HIV success. To truly explain what national policies "worked," in addition to HIV prevalence data, evidence or estimates are needed on HIV incidence trends, associated behavior changes, implemented interventions promoting those changes, and policies driving those interventions. Rarely, however, are there conclusive data for these components, as illustrated by the continuing debates around "what worked" in Uganda's HIV success. Unfortunately, within such debates, the understanding of the nature of the evidence requirements is often lost. Only by understanding the nature of the evidence, and how pieces of evidence fit together, can we truly reach evidence-based agreement and draw appropriate lessons of "what worked" in any case of HIV/AIDS prevention.