Understanding and predicting species extinctions and coextinctions is a major goal of ecological research in the face of a biodiversity crisis. Typically, models based on network topology are used to simulate coextinctions in mutualistic networks. However, such topological models neglect two key biological features of species interactions: variation in the intrinsic dependence of species on the mutualism, and variation in the relative importance of each interacting partner. By incorporating both types of variation, we developed a stochastic coextinction model capable of simulating extinction cascades far more complex than those observed in previous topological models. Using a set of empirical mutualistic networks, we show that the traditional topological model may either underestimate or overestimate the number and likelihood of coextinctions, depending on the intrinsic dependence of species on the mutualism. More importantly, contrary to topological models, our stochastic model predicts extinction cascades to be more likely in highly connected mutualistic communities.