Mutualisms are key components of biodiversity and ecosystem function, yet the forces maintaining them are poorly understood. We investigated the effects of removing large mammals on an ant-Acacia mutualism in an African savanna. Ten years of large-herbivore exclusion reduced the nectar and housing provided by plants to ants, increasing antagonistic behavior by a mutualistic ant associate and shifting competitive dominance within the plant-ant community from this nectar-dependent mutualist to an antagonistic species that does not depend on plant rewards. Trees occupied by this antagonist suffered increased attack by stem-boring beetles, grew more slowly, and experienced doubled mortality relative to trees occupied by the mutualistic ant. These results show that large mammals maintain cooperation within a widespread symbiosis and suggest complex cascading effects of megafaunal extinction.