BACKGROUND: Few of the many behavioral sexual health interventions in Africa have been rigorously evaluated. Where biological outcomes have been measured, improvements have rarely been found. One of the most rigorous trials was of the multi-component MEMA kwa Vijana adolescent sexual health programme, which showed improvements in knowledge and reported attitudes and behaviour, but none in biological outcomes. This paper attempts to explain these outcomes by reviewing the process evaluation findings, particularly in terms of contextual factors. METHODS: A large-scale, primarily qualitative process evaluation based mainly on participant observation identified the principal contextual barriers and facilitators of behavioural change. RESULTS: The contextual barriers involved four interrelated socio-structural factors: culture (i.e. shared practices and systems of belief), economic circumstances, social status, and gender. At an individual level they appeared to operate through the constructs of the theories underlying MEMA kwa Vijana - Social Cognitive Theory and the Theory of Reasoned Action - but the intervention was unable to substantially modify these individual-level constructs, apart from knowledge. CONCLUSION: The process evaluation suggests that one important reason for this failure is that the intervention did not operate sufficiently at a structural level, particularly in regard to culture. Recently most structural interventions have focused on gender or/and economics. Complementing these with a cultural approach could address the belief systems that justify and perpetuate gender and economic inequalities, as well as other barriers to behaviour change.