This article reports on the preliminary findings of a qualitative research study that explored the perceptions of five directors of education in Manitoba's First Nations' educational authorities as they assess prospective teachers for fit for both their schools and their local communities. The findings of this study illustrate that in order to meet the challenges of teaching effectively in First Nations' schools, those responsible for hiring teachers want to find candidates who (a) contribute to the establishment of a new culture of teaching in the schools, (b) form respectful relationships with students and other members of the particular First Nation community, (c) possess a worldview that is commensurate with those held by First Nations peoples, and (d) are competent to teach academic subjects and also support students' development as Indigenous youth. I conclude with recommendations that can support the preparation of a greater number of prospective teachers capable of teaching effectively in First Nation schools.