Gender-based violence (GBV) is a global health issue that affects significant proportions of women and girls. Despite research showing that children understand and perform stereotypical gender norms from as young as 3 years, addressing gender with young children is controversial. Programs that aim to teach gender fairness and respectful relationships in early childhood settings are uncommon. This article reports on an evaluation of a trial of a whole of service approach to the teaching of gender equity with a group of early childhood services in Melbourne, Australia. The project resulted in many changes in professional practice including applying a gender lens to planning practices and making changes to the resources provided in children's learning spaces. This research has important implications for how gender equity might be taught with young children and the support that early childhood educators need to implement these changes.