Global change and governance scholars frequently highlight polycentricity as a feature of resilient governance, but both theoretical and empirical knowledge about features and outcomes of the concept are lacking at the global scale. Here we investigate the structural properties of governance of global nitrogen (N) and phosphorus (P) cycles, two processes in the 'planetary boundaries' framework. We have used a mixed-methods approach to institutional analysis, integrating polycentric theory with social network theory in environmental policy and legal studies. We include an actor collaboration case study, the Global Partnership on Nutrient Management (GPNM), to explore governance challenges associated with global N and P cycles. We set the scope for selection of relevant legal instruments using an overview of global N and P flows between Earth system 'components' (land, water, atmosphere, oceans, biosphere) and the major anthropogenic N and P perturbations. Our network analysis of citations of global N and P governance exposes the structural patterns of a loose network among the principal institutions and actors, in which legal instruments of the European Union serve as key cross-scale and cross-sectoral 'gateways'. We show that the current international regimes in place for regulating N- and P-related issues represent a gap in governance at the global level. In addition, we are able to show that the emergence of GPNM provides synergies in this context of insufficient governance. The GPNM can be viewed as a structure of polycentric governance as it involves deliberate attempts for mutual adjustments and self-organised action.