The Health and Physical Education (HPE) profession has increasingly advocated for caring teacher-student relationships. In this paper, we draw on data from an international research project called 'EDUHEALTH' [Education for Equitable Health Outcomes -- The Promise of School Health and Physical Education] to explore caring teaching and the complexity of building good relationships as pedagogies for social justice in HPE. The data reported on in this paper were generated through 20 HPE lesson observations and interviews with 13 HPE teachers across schools in Sweden, Norway and New Zealand. In our analysis of the data, we employed Nel Noddings 'Care Theory' [(1984. "Caring, a feminine approach to ethics & moral education." Berkeley, CA: University of California Press; 1997). Pedagogisk filosofi [Philosophy of education]. Oslo: Ad Notam Gyldendal] to study the constitution of relationships and caring teaching in HPE practice. The findings demonstrate that caring teaching is inevitably built on developing good relationships, and that developing such good relationships is a complex process influenced by three key elements. First, teachers have to develop knowledge about their students on a societal, group and personal level; second, teachers have to reflect on the individual, environmental and relational aspects required for building good relationships; and third, teachers have to implement caring teaching strategies, such as planning, caring actions and doing 'the little things'. Drawing on Nodding's care theory, we conclude that pedagogies for social justice are enacted when teachers use their own knowledge and knowledge about the students, together with reflection and caring teaching strategies, to arrange a learning environment that promotes inclusion and equitable outcomes for all students.