The links between gender roles, gender-based violence and HIV/AIDS risk are complex and culturally specific. In this qualitative study we investigated how women and men in two black communities in the Western Cape, South Africa, constructed their gender identities and roles, how they understood gender-based violence, and what they believed about the links between gender relations and HIV risk. First we conducted 16 key informant interviews with members of relevant stakeholder organisations. Then we held eight focus group discussions with community members in single-sex groups. Key findings included the perception that although traditional gender roles were still very much in evidence, shifts in power between men and women were occurring. Also, gender-based violence was regarded as a major problem throughout communities, and was seen to be fuelled by unemployment, poverty and alcohol abuse. HIV/AIDS was regarded as particularly a problem of African communities, with strong themes of stigma, discrimination, and especially 'othering' evident. Developing effective HIV/AIDS interventions in these communities will require tackling the overlapping as well as divergent constructions of gender, gender violence and HIV which emerged in the study.