The teacher-student relationship plays an important role in the academic and behavioral development of primary school children with externalizing problem behavior. However, such problem behavior often threatens the quality of the teacher-student relationship. Teacher-focused coaching intervention Key2Teach aims to improve elements of the relationship between teachers and students with externalizing problem behavior and consists of two phases and four building blocks. This intervention provides primary school teachers with insight into their mental representation of the relationship and opportunities to practice functional interaction skills. In a randomized controlled trial (RCT), effects of Key2Teach on different aspects of the relationship between teachers and students with externalizing problem behavior were examined. In two cohorts, 103 dyads consisting of a teacher and a student with externalizing problem behavior in grades 3–6 were assessed three times during a school year. Fifty-three dyads received the intervention (intervention group), whereas 50 dyads received no intervention (control group). Data were collected on teacher-reported teacher-student closeness and conflict, and on teacher interaction skills in various domains. Results show a significant increase in closeness and a decrease in conflict as a result of Key2Teach, with substantial effect sizes. No effects on teacher interaction skills were found. This study indicates that Key2Teach may help teachers to improve elements of the relationship they have with students with externalizing problem behavior. Implications for practice and future research are discussed.