Habitat loss can trigger cascades of secondary extinctions, changing the organization of interacting assemblages. Until recently, most extinction models in interaction systems had limited ecological realism. Here, we estimate a realistic sequence of species extinctions resulting from habitat loss to assess its impacts on the structure of frugivory networks from the Brazilian Atlantic Forest. We show that realistic and random extinctions led to similar patterns. We also identified a threshold in the response of network structure to habitat loss. When forest cover was reduced to less than 40% of the landscape, network organization changed dramatically. Hence, the number of species being lost, rather than the order of species extinctions, is the key determinant of its impacts on the organization of frugivory networks. We highlight the need to conserve around 40% of forest cover to keep the basic organization of frugivory networks, a threshold already reached at the best-preserved Brazilian Atlantic Forest bioregion.