Given the need for transformative changes towards more sustainable, integrated management of water, energy and food systems, the water-energy-food nexus concept seems highly relevant. However, while intuitively compelling, the nexus has also been criticized for abstracting and thereby dis-embedding the collaboration processes through which further integration could be achieved. There is a lack of empirical analysis and context-sensitive understanding, of the opportunities and constraints of, collaboration and cross-sector coordination, as faced by actors governing interconnected water, energy and food systems. In this paper we analyse how actors involved in the governance of water, energy and food systems are embedded in social networks, and discuss how that embeddedness shapes collaboration and coordination processes that are relevant for addressing interconnected sustainability challenges. Drawing on the notion of problemsheds, we delineate an analytical space that captures the interactions between water, energy and food systems and the actors influencing them in the Upper Blue Nile of Ethiopia. Our empirical data suggest that the claim that actors from different sectors are disconnected from each other is overly simplistic. The ways in which actors are embedded in hierarchical structures may help to explain why coordination challenges persist, despite the presence of cross-sectoral linkages among them.