Pollination by animals is a key ecosystem service1,2 and interactions between plants and their pollinators are a model system for studying ecological networks,3,4 yet plant-pollinator networks are typically studied in isolation from the broader ecosystems in which they are embedded. The plants visited by pollinators also interact with other consumer guilds that eat stems, leaves, fruits, or seeds. One such guild, large mammalian herbivores, are well-known ecosystem engineers5, 6, 7 and may have substantial impacts on plant-pollinator networks. Although moderate herbivory can sometimes promote plant diversity,8 potentially benefiting pollinators, large herbivores might alternatively reduce resource availability for pollinators by consuming flowers,9 reducing plant density,10 and promoting somatic regrowth over reproduction.11 The direction and magnitude of such effects may hinge on abiotic context—in particular, rainfall, which modulates the effects of ungulates on vegetation.12 Using a long-term, large-scale experiment replicated across a rainfall gradient in central Kenya, we show that a diverse assemblage of native large herbivores, ranging from 5-kg antelopes to 4,000-kg African elephants, limited resource availability for pollinators by reducing flower abundance and diversity; this in turn resulted in fewer pollinator visits and lower pollinator diversity. Exclusion of large herbivores increased floral-resource abundance and pollinator-assemblage diversity, rendering plant-pollinator networks larger, more functionally redundant, and less vulnerable to pollinator extinction. Our results show that species extrinsic to plant-pollinator interactions can indirectly and strongly alter network structure. Forecasting the effects of environmental change on pollination services and interaction webs more broadly will require accounting for the effects of extrinsic keystone species.