There are many documented barriers to implementing school-based sustainability. This article examines a) the barriers faced by principals and staff in two regional primary schools in Far North Queensland, Australia, well known for their exemplary practice, and b) ways the barriers were overcome. Through interviews conducted with principals and key staff, the authors found lack of time, direct funding for innovation, teacher conceptual understanding, resistance from some fellow staff to sustainability education, and being positioned as a "greenie" were presented as barriers to effective practice. The research reveals how innovation, determination, trust, and active principal support enabled the teachers to push ahead. Other educators experiencing difficulties with implementing sustainability education will likely find the discussion useful.