Navigating complexity for change toward sustainability in large companies is best done using a systems perspective, a principled vision of success and a step-wise planning process, as espoused for instance by the Framework for Strategic Sustainable Development. Many large companies have a significant contribution to un-sustainability and stand to benefit from such a transition. However, the human factor of the undertaking is as of yet underdeveloped in extant literature. Seeking insights into experiences of sustainability change-agents in large companies, the authors conducted 20 semi-structured interviews with sustainability change- agents in large companies. Using a relational view as an analytical lens, they examined the dynamics of social interactions involving these change-agents and thereby gained a greater understanding of the place held by these individuals in the broader company system. The 11 relational categories that emerged permitted to draw links between structural, behavioural and personal facets of advancing sustainability in large companies and highlighted the human aspect of strategic planning as well as the strategic nature of building relationships, teams and coalitions. Overall, the authors believe that consideration by the change-agents of relational aspects may help foster commitment and collaboration in the transition toward sustainability