This paper explores young people's understandings of gender and investigates their gender-based experiences in high schools in Australia. The discussion is based on qualitative research including focus groups and interviews with 47 recent high school leavers from diverse linguistic, socioeconomic, religious, ethnic, gender and sexuality backgrounds, who attended a broad range of high school types in New South Wales (NSW). We found that young people are critically engaging in gender issues and are often challenging binary gender and associated inequitable practices in schools and beyond. They are taking a leading role in educating adults about gender--that is, they are 'teaching up', as young people conceptualised it, to their families and teachers about gender, gender-related issues and doing gender differently in contemporary times. Their views on gender are often in contrast to those institutional views that currently prevail in NSW schools, which often still reflect stereotypes that perpetuate gender inequalities.