HIV prevention research has shifted to the evaluation of combination prevention programs whereby biomedical, behavioral, and structural interventions are implemented concurrently to maximize synergies among interventions. However, these kinds of combination prevention packages, particularly when implemented at scale, pose significant evaluation challenges, including how best to determine impact and how and whether to measure the effectiveness of component strategies. In addition, methodological challenges unique to HIV infection such as the absence of a reliable incidence assay, the lack of naive control groups, and no suitable surrogates further complicate rigorous evaluation. In this commentary, we discuss the key considerations for planning impact evaluations of combination HIV prevention programs in light of these challenges, including defining the evaluable package, determining which component programs require independent assessment of impact, choosing study designs with valid counterfactuals, selecting appropriate outcomes of interest, and the importance of mid-course program corrections.