Instructional leadership is an educational leadership model in which principals are directly and continually involved in curricular and instructional issues. This study aimed to identify the relationships needed for principals' instructional leadership, a topic that has not been sufficiently explored. Participants of this qualitative study were 26 Israeli school principals. Data were collected through semi-structured interviews. Findings suggest that instructional leaders do not only focus on ensuring that educational work is carried out adequately but also on intrapersonal and interpersonal relationships. The basis for instructional leadership is four relationships that principals need to cultivate: (1) with themselves; (2) with school middle leaders; (3) with teachers; and (4) with external stakeholders. Implications and further research are discussed.