Why are large, complex ecosystems stable? Both theory and simulations of current models predict the onset of instability with growing size and complexity, so for decades it has been conjectured that ecosystems must have some unidentified structural property exempting them from this outcome. We show that trophic coherence – a hitherto ignored feature of food webs which current structural models fail to reproduce – is significantly more correlated with stability than are size or complexity. Furthermore, we prove that a maximally coherent network will always be stable. We also propose a simple model which, by correctly capturing the trophic coherence of food webs, accurately reproduces their stability and other basic structural features. Most remarkably, our model shows that stability can increase with size and complexity. This suggests a key to May’s Paradox, and a range of opportunities and concerns for biodiversity conservation.