A growing field of sustainability science examines how environments are transformed through polycentric governance. However, many studies are only snapshot analyses of the initial design or the emergent structure of polycentric regimes. There is less systematic analysis of the longitudinal robustness of polycentric regimes. The problem of robustness is approached by focusing not only on the structure of a regime but also on its context and effectiveness. These dimensions are examined through a longitudinal analysis of the Great Barrier Reef (GBR) governance regime, drawing on in-depth interviews and demographic, economic, and employment data, as well as organizational records and participant observation. Between 1975 and 2011, the GBR regime evolved into a robust polycentric structure as evident in an established set of multiactor, multilevel arrangements addressing marine, terrestrial, and global threats. However, from 2005 onward, multiscale drivers precipitated at least 10 types of regime change, ranging from contextual change that encouraged regime drift to deliberate changes that threatened regime conversion. More recently, regime realignment also has occurred in response to steering by international organizations and shocks such as the 2016 mass coral-bleaching event. The results show that structural density and stability in a governance regime can coexist with major changes in that regime’s context and effectiveness. Clear analysis of the vulnerability of polycentric governance to both diminishing effectiveness and the masking effects of increasing complexity provides sustainability science and governance actors with a stronger basis to understand and respond to regime change.