Despite the resources put into HIV education programmes with young people in sub-Saharan Africa in the past two decades, there is little clear evidence of impact. Many programmes continue to be oriented towards individual behaviour change (and in reality, often sexual abstinence) with insufficient focus on understanding how societies constrain or enable individual agency in sexual decision-making and how this is affected by social norms. If education programmes do address gender they often reinforce a “male perpetrator, female victim” discourse, where girls and women are held responsible for boys' and men's sexuality as well as their own. This paper discusses the discourses around gender, sexuality and HIV constructed by young women and men (aged 16–29) in a rural Eastern Zambia village. Data on young women's and men's narratives were gathered using a participatory peer approach. Research uncovered numerous and sometimes conflicting discourses (cultural, moral, economic, and sexual) influencing young women's and men's thinking about sexuality and sexual behaviour, in particular the limited possibilities for safe consensual sex, and thus their vulnerability to HIV. The research suggests that the realities young people face are much more complex than HIV prevention strategies address. We recommend a more nuanced approach, tailored to the community contexts involved.