A central problem in ecology is to understand how human impacts affect plant-animal interactions that lead to effective seed dispersal services for plant communities. Seed dispersal services are the outcome of plant-frugivore interactions that often form local networks of interacting species. Recent work has shown that some frugivorous bird species are more critical to network organization than others. Here, we explore how patch size and the potential local extinctions of obligate frugivorous birds affect the reorganization of seed dispersal networks. We examined the structure of 20 empirical seed dispersal networks documented across tropical avian assemblages occupying widely variable habitat patch sizes, a surrogate of the amount of remaining habitat. Networks within small forest patches consistently supported both lower plant and bird species richness. Forest patch size was positively associated with nestedness, indicating that reductions in patch size disrupted the nested organization of seed dispersal networks. Obligate frugivores, especially large-bodied species, were almost entirely absent from small forest patches. Analysis at the species level showed that obligate frugivores formed the core of interacting species, connecting species within a given seed dispersal network. Our combined results revealed that patch size reduction erodes frugivorous bird diversity, thereby affecting the integrity of seed dispersal networks. We highlight the importance of conserving large forest patches to maintain tropical forest functionality.