Education is identified as the main proponent for achieving sustainability on individual, community, national, and global scales. Education for Sustainability (EfS) (education that promotes sustainable thought and practice) has not yet gained momentum in Australia, despite Australia’s commitment to the United Nation’s Decade of Education for Sustainable Development and signing of the Talloires Declaration. Primary and secondary research was conducted to explore barriers to the implementation of EfS in Australian primary, secondary, and tertiary institutions, with a focus on Australian public higher education. Major barriers identified were lack of government funding and support; lack of teacher pre-service education; and lack of in-service education. This paper also explores barriers to sustainable behaviour change on an individual level; the main barriers being the effects of psychology on sustainable behaviour (in particular, Unconscious Thought Theory and Confirmation Bias were discussed), cultural irrelevance, and communication language. Results were compiled to inspire the preliminary design of a proposal for the Tertiary Education Quality Standards Agency, an Australian Federal Government regulatory body that oversees the higher education sector, to integrate EfS into public tertiary curricula. The proposal is guided by Doug McKenzie-Mohr’s Community-Based Social Marketing Framework and the Social Impact Framework developed by the Australian Centre for Social Impact. To improve the effectiveness and validity of the proposal, further research is needed in the areas of curriculum standards, institutional barriers, demographics, government policy and funding, and international initiatives.