The conventional piecemeal approach to environmental treaty-making has resulted in a ‘maze’ of international agreements. However, little is known empirically about its overall structure and evolutionary dynamics. This study reveals and characterizes the evolving structure of the web of international environmental treaty law. The structure was approximated using 1001 cross-references among 747 multilateral environmental agreements concluded from 1857 to 2012. Known network analysis measures were used to answer the following questions: has a complex system of international environmental treaty law emerged? If so when, and what does it look like? What are its topological properties? To what extent is the institutional complex fragmented? The network analysis suggested that multilateral environmental agreements have self-organized into an interlocking system with a complex network structure. Furthermore, the system has defragmented as it coevolved with the increasing complexity and interconnectivity of global environmental challenges. This study demonstrates the need to approach multilateral environmental agreements in the context of a complex networked system, and recommends against assuming the overall institutional structure is fragmented. Proposals for global environmental governance reform should pay attention to this network’s emergent polycentric order and complexity and to the implications of these features for the functioning of the multilateral environmental agreement system.