Many ecosystem functions result from mutualisms, yet mutualism-based functions have rarely been studied at the scale of whole mutualist networks. Thus, it is unclear how much biodiversity is needed to provide function to an entire network of partner species. Here we use 23 plant-pollinator networks to ask how the number of functionally important pollinator species depends on the number of plant species studied. We found that, because of complementarity among pollinators in the plants they pollinate, 3-13 times as many pollinator species were needed to pollinate an entire network as compared with a single plant species. Furthermore, many pollinator species that were rare within the network as a whole, and therefore not important pollinators on average, were important to the pollination of particular plant species. By not measuring function across entire mutualist networks, ecologists have likely underestimated the importance of biodiversity, and particularly of rare species, for ecosystem function.