The coaching relationship is seen as integral to individual coaching, but less is known about the nature of the relationship within a team coaching context. This study explores the importance that leadership team coaching practitioners attach to the coaching relationship and as a consequence what that means for how they work with teams. A qualitative single case study method was utilised and data gathered using semi-structured interviews, including critical incident technique. The overall finding from the research was that coaches considered it important to develop a trust-based relational connection with teams at both an individual and a collective level but that establishing and maintaining that connection was, at times, both complex and challenging.