Our planet is changing at paces never observed before. Species extinction is happening at faster rates than ever, greatly exceeding the five mass extinctions in the fossil record. Nevertheless, our lives are strongly based on services provided by ecosystems, thus the responses to global change of our natural heritage are of immediate concern. Understanding the relationship between complexity and stability of ecosystems is of key importance for the maintenance of the balance of human growth and the conservation of all the natural services that ecosystems provide. Mathematical network models can be used to simplify the vast complexity of the real world, to formally describe and investigate ecological phenomena, and to understand ecosystems propensity of returning to its functioning regime after a stress or a perturbation. The use of ecological-network models to study the relationship between complexity and stability of natural ecosystems is the focus of this review. The concept of ecological networks and their characteristics are first introduced, followed by central and occasionally contrasting definitions of complexity and stability. The literature on the relationship between complexity and stability in different types of models and in real ecosystems is then reviewed, highlighting the theoretical debate and the lack of consensual agreement. The summary of the importance of this line of research for the successful management and conservation of biodiversity and ecosystem services concludes the review.