Forty years ago, Robert May questioned a central belief in ecology by proving that sufficiently large or complex ecological networks have probability of persisting close to zero. To prove this point, he analyzed large networks in which species interact at random. However, in natural systems pairs of species have well-defined interactions (e.g., predator-prey, mutualistic or competitive). Here we extend Mays results to these relationships and find remarkable differences between predator-prey interactions, which increase stability, and mutualistic and competitive, which are destabilizing. We provide analytic stability criteria for all cases. These results have broad applicability in ecology. For example, we show that, surprisingly, the probability of stability for predator-prey networks is decreased when we impose realistic food web structure or we introduce a large preponderance of weak interactions. Similarly, stability is negatively impacted by nestedness in bipartite mutualistic networks.