In recent years, restorative justice (RJ) has been increasingly embedded in school policies and practice, primarily as a method to correct individual behavior. RJ, however, has a deeper potential, to help students build relationships and make school safe, equitable and relevant for its members. RJ is a growing social movement -- globally and in Canada -- that practices peaceful, constructive approaches to violations of legal and human rights. Yet, there is little understanding for how to introduce RJ to teachers so that they are supported to tap into this deeper potential in a sustainable manner. This manuscript provides a discussion of RJ as it is currently understood, implemented, and institutionalized, and we present data collected via focus groups with former teacher candidates enrolled in an RJ-focused teacher education course facilitated through relational pedagogy. The data highlights participants' perceptions of RJ, the relational pedagogy approach of the course and the impact of the course on participants' learning experiences. We draw from this data to make a case for embedding the philosophies of RJ and relational pedagogy into teacher education classrooms in order for teacher candidates to develop relationship-building competencies and a capacity to implement RJ in effective, holistic and sustainable ways.