Social parasites exploit societies, rather than organisms, and rear their brood in social insect colonies at the expense of their hosts, triggering a coevolutionary process that may affect host social structure. The resulting coevolutionary trajectories may be further altered by selection imposed by predators, which exploit the abundant resources concentrated in these nests. Here, we show that geographic differences in selection imposed by predators affects the structure of selection on coevolving hosts and their social parasites. In a multi-year study, we monitored the fate of the annual breeding attempts of the solitary-founding females of Polistes biglumis social wasps in four geographically distinct populations that varied in levels of attack by the congeneric social parasite, P. atrimandibularis. Foundress fitness depended mostly on whether, during the long founding phase, a colony was invaded by social parasites or attacked by predators. Foundresses from each population differed in morphological traits and reproductive tactics that were consistent with selection imposed by their natural enemies and in ways that may affect host sociality. In turn, parasite traits were consistent with selection imposed locally by hosts, implying a geographic mosaic of coevolution in this brood parasitic interaction.