Governance processes to address environmental change involve many different actors from multiple spatial, temporal and socio-political scales, not all of whom are connected by hierarchy and whose actions cannot always be mandated. In the environmental governance literature, Social Network Analysis (SNA) has been found useful in understanding complex governance arrangements. In this paper we present and reflect on our experience with the Net-Map tool for participatory network mapping. The Net-Map tool was applied in three transdisciplinary case studies for three different purposes: (a) to contribute to an improved understanding of biodiversity knowledge flows in Europe, (b) to explore the interplay between actors with influence on water, agriculture, and energy developments at the Blue Nile in Ethiopia, and (c) to understand the challenges facing stakeholders engaged in conservation and economic development in a Southeast Asian mountain range. The case studies explore how network maps can serve as boundary objects to engage stakeholders of diverse points of view and jointly design strategies to address governance challenges. More specifically they show how network maps are used to gain a better understanding of governance situations, to help stakeholders identify strategies for navigation of the complex networks in which they are embedded and to support transdisciplinary research processes. We close with some reflections on the potential and limitations of the Net-Map tool in facilitating multi-stakeholder processes and disentangling complex governance arrangements.