Gender-based violence is a widespread problem in South Africa. Past structural inequities have created a climate conducive to violence against women. As an initial step toward developing a health promotion program, we conducted exploratory formative research to examine the barriers that affect the health and well-being of youth. Fourteen focus groups (nine with girls and five with boys) were conducted with 112 adolescents in a racially mixed community on the outskirts of Cape Town, South Africa. We utilized grounded theory and thematic analysis to examine the data. The impact of poverty, ubiquitous gendered violence, transactional sex and unsafe recreational spaces emerged as the major themes. The experiences of youth were consumed by issues of safety rather than the pursuit of other developmentally appropriate markers. Our findings suggest that health promotion programs should create safe spaces for youth and opportunities to critically question the assumptions and manifestations of a patriarchal society. Furthermore, the findings indicate that there is a strong need for multi-sectorial interventions directed at many levels to prevent gender-based violence.