Forty years ago, May proved1,2that sufficiently large or complex ecological networks have a probability of persisting that is close to zero, contrary to previous expectations3,4,5. May analysed large networks in which species interact at random1,2,6. However, in natural systems pairs of species have well-defined interactions (for example predator–prey, mutualistic or competitive). Here we extend May’s results to these relationships and find remarkable differences between predator–prey interactions, which are stabilizing, and mutualistic and competitive interactions, which are destabilizing. We provide analytic stability criteria for all cases. We use the criteria to prove that, counterintuitively, the probability of stability for predator–prey networks decreases when a realistic food web structure is imposed7,8or if there is a large preponderance of weak interactions9,10. Similarly, stability is negatively affected by nestedness11,12,13,14in bipartite mutualistic networks. These results are found by separating the contribution of network structure and interaction strengths to stability. Stable predator–prey networks can be arbitrarily large and complex, provided that predator–prey pairs are tightly coupled. The stability criteria are widely applicable, because they hold for any system of differential equations.