In South Africa, both HIV and gender-based violence are highly prevalent. Gender inequalities give men considerable relational power over young women, particularly in circumstances of poverty and where sex is materially rewarded. Young women are often described as victims of men, but this inadequately explains women's observed sexual agency. This paper takes a different approach. The authors use qualitative interviews and ethnographic observation among 16 young women from the rural Eastern Cape to explore ways young women construct their femininities and exercise agency. The data were collected as part of an evaluation of Stepping Stones, which is a participatory behavioural intervention for HIV prevention that seeks to be gender transformative. Agency was most notable in particular stages of the dating 'game', especially relationship initiation. Constructions of desirable men differed but generally reflected a wish to avoid violence, and a search for mutual respect, sexual pleasure, romance, modernity, status and money. Agency was constrained once relationships were consented to, as men expected to control their partners, using violent and non-violent methods. Women knew this and many accepted this treatment, although often expressing ambivalence. Many of the women expressed highly acquiescent femininities, with power surrendered to men, as a 'choice' that made their lives in cultural terms more meaningful. In marked contrast to this was a 'modern' femininity, centred around a desire to be 'free'. A visible third position, notably emerging after the Stepping Stones intervention, rested not on a feminist challenge to patriarchy, but on an accommodation with men's power whilst seeking to negotiate greater respect and non-violence within relations with men. These multiple and dynamic femininities open up possibilities for change. They demonstrate the need to engage with women, both as victims of patriarchy and active supporters of the gender order. The multiplicity of women's hopes and desires and circumstances of emotional and relational fulfillment provides potential for interventions with women that acknowledge existing gender inequalities, validate women's agency, reduce violence and prevent HIV.