This Australian case study provides a snapshot of Education for Sustainability (EfS) practice of early years teachers in the school sector (Preparatory to Year 3), during the first phase of implementation of the Australian national curriculum. Interviews with teachers, located in government, Catholic and independent schools, were conducted by pre-service teachers as a part of their professional experience coursework requirements. Forty-three interview transcripts were collated in these qualitative analyses in order to explore: why teachers considered that EfS had been identified as a cross-curriculum priority in the national curriculum; how teachers implemented EfS in their classrooms; and the barriers that they experienced in implementation. The teachers perceived EfS to be highly relevant to their students, with a view to future participation in society, workplaces, leadership and lifelong learning. While the majority of teachers reported intentionally planning and implementing learning experiences that addressed aspects of EfS, the key barrier from their perspective was a crowded curriculum, with emphasis on literacy and numeracy performance. Findings reveal that ongoing professional learning is required for teachers to develop pedagogies that can promote students' critical and action-oriented engagement, with community partners, in local socio-ecological issues of relevance, whether in urban, rural or remote locales.