Promotion of gender equality is a key millennium goal, yet gender inequities permeate all levels of society, from the macro, structural level in legal systems and economies, to the community level where social expectations based on gender stereotypes act as a powerful force determining behaviour. Is it possible for small-scale interventions to alter gender relations where social inequality is so widespread and entrenched? This ethnographic study of a sexual health intervention in Mexico shows how gender relations were improved and the "gender gap" reduced among young people participating in the intervention. The study used participant observation in the programme and community over one year in a low-income area of Mexico City, combined with data from 154 in-depth interviews with unmarried young people both involved in the programme and outside the programme. The most striking change in young people participating in the programme over time, and the difference between participants and non-participants was the improved ability of participants to communicate with members of the opposite sex, their critical analysis of gender stereotypes, and their increased understanding of their own involvement in the reinforcement of gender stereotypes and desire to reduce this involvement. The differences manifested themselves in the ways that the young people communicated their ideas and desires, their attitudes towards sexuality and sexual behaviour, and their relationships with their partners. The paper discusses the effects of the programme on the young participants, and provides an examination of the processes of the programme to which these effects may be attributed. Finally, it identifies key elements of the programme influencing gender relations that could be transposed to other settings.