Mutualisms are important ecological interactions that underpin much of the world’s biodiversity. Predation risk has been shown to regulate mutualism dynamics in a number of species-specific case studies. Surprisingly, however, we lack studies which investigate whether selection by predators can also explain broader patterns of mutualism evolution. We report that fish-anemone mutualisms have evolved on at least 48 independent occasions across 16 fish families over the past 60 MY 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 preferentially target smaller prey, that smaller individuals more commonly associate with anemones, and that these relationships confer increased protection to small fishes. Our results indicate that predation is the most likely pressure 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.