Campus Kindergarten in Brisbane, Australia, is a community-based organisation for children and families that has embraced change through the evolution of its internationally acclaimed ‘Sustainable Planet Project’. The centre initiated the project in 1997, introducing a range of new curriculum and pedagogical processes - always with young children at the heart - that have led to improvements in play spaces, reduced waste, lowered water consumption and improved biodiversity. This child-focussed approach is reflected in the way that children’s ideas provide much of the motivation and inspiration for changing to more sustainable practices. A whole centre project on water conservation, for example, was sparked when preschoolers (aged 4 years) articulated their concerns to staff about water use in the sandpit. This paper overviews a recent research project designed to document, examine and highlight the Sustainable Planet Project, to assist centre staff, researchers and others with a commitment to sustainability, to understanding the change processes. An important feature has been the project's slow, sometimes erratic, development that has always added complexity to the teachers’ work. Such change, however, has not been viewed negatively. Complexity theory has helped to explain the project’s evolution and complexity has been embraced as a vehicle for creativity, engagement, critique and ongoing change in this learning organisation. As a consequence, a culture of sustainability now permeates the centre where a strong vision has been translated into small but realistic goals and achievements.