What makes the collections of international institutions or regimes governing various domains—called in the literature regime, institutional, or governance complexes—"complex"? This article examines several conditions for complexity discussed in that literature and finds them necessary but not sufficient. It argues that the sufficient condition is dependence and outlines a framework of increasing levels of synchronic (social/spatial) and diachronic (temporal) dependence. Putting dependence at the centre of discussions on regime complexes has four advantages: (1) it is analytically more precise a condition than proliferation or linkage; (2) it orients us toward questions of degree, 'how complex', instead of the binary 'whether complex'; (3) it informs a range of research design and theoretical choices, especially highlighting extra-dyadic dependencies and an underdeveloped temporal dimension; and (4) it arguably reconciles competing uses of the term "complex" in the literature without conflating it with complexity, structure, or topology.