Does an ecological community allow stable species coexistence? Identifying the general effects of competitive, mutualistic, and predator-prey interactions on stability remains a central problem of systems ecology because established approaches cannot account for the full network arrangement of these interactions. Here, we therefore analyze all interaction networks of N≤5 species with Lotka-Volterra dynamics by combining exact results and numerical exploration. We find that a very small subset of these networks is “impossible ecologies,” in which stable coexistence is non-trivially impossible. We prove that the possibility of stable coexistence is determined by similarly rare “irreducible ecologies.” Statistical sampling shows that this probability varies over orders of magnitude even in ecologies that differ only in the network arrangement of identical interactions. Thus, our approach reveals that the full network structure of interactions can influence stability of coexistence more than the established effect of interaction-type proportions. A record of this paper's transparent peer review process is included in the supplemental information.