A major problem in evolutionary biology is explaining the success of mutualism. Solving this problem requires understanding the level of fidelity between interacting partners. Recent studies have proposed that fungus-growing ants and their fungal cultivars are the products of 'diffuse' coevolution, in which single ant and fungal species are not exclusive to one another. Here we show for ants and associated fungi in the Cyphomyrmex wheeleri species group that each ant species has been exclusively associated with a single fungal cultivar 'species' for millions of years, even though alternative cultivars are readily available, and that rare shifts to new cultivars are associated with ant speciation. Such long-term partner fidelity may have facilitated 'tight' ant-fungus coevolution, and shifts to new fungal cultivars may have had a role in the origin of new ant species.