This paper explores the form and extent of sustainability uptake in education policy in First Nations-managed K-12 schools, and discusses strategies First Nations' educational communities use to overcome barriers encountered in sustainability education practice. Interviews were conducted with educators across four different Canadian schools and content analysis was used to draw out key themes of analysis. These include educators' articulations of relationships to land, including a relational legacy of living in an implicitly sustainable and respectful way. Participants also described how culturally and geographically relevant pedagogical approaches to sustainability are challenged by systemic and localized barriers. Participants perceived that under-resourcing and administrative challenges limit the integration of sustainability across curricular areas, hindering educators' abilities to develop appropriate innovative programming and resources for First Nations' students. They have been able to overcome these obstacles, to some extent, by harnessing community resources to indirectly include sustainability in the curriculum. Implications for educators, policy makers, and agencies are discussed.