Mutualisms are important ecological interactions that underpin much of the world’s biodiversity. Predation risk has been shown to regulate mutualism dynamics in species-specific case studies; however, we lack studies which investigate whether predation can also explain broader patterns of mutualism evolution. We report that fish-anemone mutualisms have evolved on at least 55 occasions across 16 fish families over the past 60 million years and that adult body size is associated with the ontogenetic stage of anemone mutualisms: larger-bodied species partner with anemones as juveniles, while smaller-bodied species partner with anemones throughout their lives. Field and laboratory studies show that predators target smaller prey, that smaller fishes associate more with anemones, and that these relationships confer protection to small fishes. Our results indicate that predation is likely driving the recurrent convergent evolution of fish-anemone mutualisms and suggest that similar ecological processes may have selected convergence in interspecies interactions in other animal clades.