Many complex systems – from the Internet to social, biological, and communication networks – are thought to exhibit scale-free structure. However, prevailing explanations require networks to constantly grow, an assumption that fails in some real-world settings. Here, we propose a model in which nodes die and their connections rearrange under a mixture of preferential and random attachment. Under these simple dynamics, we show that networks self-organize towards scale-free structure, with a power-law exponent γ = 1 + 1/p that depends only on the proportion p of preferential (rather than random) attachment. Applying our model to several real networks, we infer p directly from data and predict the relationship between network size and degree heterogeneity. Additionally, we show that similar dynamics can explain the emergence of other heavy-tailed network features, such as the connection strengths in populations of neurons. Together, these results establish that scale-free structure can arise naturally as the steady-state of a simple dynamical process in networks of constant size and density.