The loss of interactions from mutualistic networks could foreshadow both plant and animal species extinctions. Yet, the characteristics of interactions that predispose them to disruption are largely unknown. We analyzed 12 pollination webs from isolated hills ("sierras"), in Argentina, ranging from tens to thousands of hectares. We found evidence of nonrandom loss of interactions with decreasing sierra size. Low interaction frequency and high specialization between interacting partners contributed additively to increase the vulnerability of interactions to disruption. Interactions between generalists in the largest sierras were ubiquitous across sierras, but many of them lost their central structural role in the smallest sierras. Thus, particular configurations of interaction networks, along with unique ecological relations and evolutionary pathways, could be lost forever after habitat reduction.