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. This paper analyses how actors involved in the governance of water, energy and food systems are embedded in social networks, and discusses how that embeddedness shapes collaboration and coordination processes that are relevant for addressing interconnected sustainability challenges. Drawing on the notion of problemsheds, an analytical space is delineated capturing the interactions between water, energy and food systems and the actors influencing them in the Upper Blue Nile of Ethiopia . 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.