Pre-exposure prophylaxis (PrEP) is an important HIV prevention method for adolescent girls and young women (AGYW) in Africa, who are at heightened risk of HIV infection. HIV risk perception is generally a powerful motivator for adoption of HIV prevention behaviours, including PrEP use. While HIV risk perceptions have been evaluated using quantitative measures, these seldom capture how individuals conceptualize and understand risk within local frameworks of meaning. More nuanced understanding may come from qualitative approaches that map these perceptions across the trajectory of sexual histories. Between 2016 and 2018, we implemented a novel participatory method to investigate risk perceptions in interviews with 32 participants in HPTN 082, a study of AGYW's use of PrEP in South Africa and Zimbabwe. Timelines were used to record narrative sexual histories and perceived HIV risk for each relationship. We found that women assessed HIV risk primarily based on their partners' personal qualities and behaviour (especially relating to infidelity); their subjective experience of being treated respectfully; and the practice of perceived 'risk reduction', including younger partners and condoms, even if used inconsistently. A narrative timeline approach grounded in an understanding of young women's sexual histories may increase critical reflection about HIV risks and facilitate risk-reduction counselling with this group.