How well do young people understand their developing sexuality and what this means? This paper reports on findings from the Our Lives: Culture, Context and Risk project, which investigated sexual behaviour and decision-making in the context of the everyday life experience and aspirations of Indigenous and non-Indigenous young people (16-25 years) in the Northern Territory, Western Australia and in South Australia. Using qualitative data, this paper focuses on what participating young people thought was necessary to improve the quality of sexuality education. Participants suggest that current forms of sexuality education are too clinical, didactic and unengaging, and are missing in relevant content. Young people requested more information on relationships, first sexual experiences and negotiating condom use. These requests indicate that young people realise that they need more knowledge in order to have healthy relationships, which conflicts with the popular belief that providing young people with open, honest information around sex will encourage them to have sex or increase sexual risk taking. Making sexuality education more of a priority and listening to the needs of young people could be a positive step towards improving sexual health and well-being.