This paper assesses the extent to which HIV prevention interventions for young people in sub-Saharan Africa are grounded in theory and if theory-based interventions are more effective. Three databases were searched for evaluation studies of HIV prevention interventions for youth. Additional articles were identified on websites of international organisations and through searching references. 34 interventions were included; 25 mentioned the use of theory. Social Cognitive Theory was most prominent (n = 13), followed by Health Belief Model (n = 7), and Theory of Reasoned Action/Planned Behaviour (n = 6). These cognitive behavioural theories assume that cognitions drive sexual behaviour. Reporting on choice and use of theory was low. Only three articles provided information about why a particular theory was selected. Interventions used theory to inform content (n = 13), for evaluation purposes (n = 4) or both (n = 7). No patterns of differential effectiveness could be detected between studies using and not using theory, or according to whether a theory informed content, and/or evaluation. We discuss characteristics of the theories that might account for the limited effectiveness observed, including overreliance on cognitions that likely vary according to type of sexual behaviour and other personal factors, inadequately address interpersonal factors, and failure to account for contextual factors.