In young children's worlds, gender and sexualities are constantly policed. Who children play with, where they play and how they play are often subject to regulation by others to perpetuate 'normativity'. This colloquium draws on 'telling examples' from an in-progress study in an early childhood education setting in Aotearoa New Zealand. Examples of challenge and resistance show several children actively constructing and performing their gender in flexible and multiple ways, some of which contest/resist traditional and cultural norms and dominant discourses. The central argument is that 'doing gender' in relationship with others is complex work for children that can be better understood through the constructs of 'performativity' and 'working theories' jointly.