The interaction structure of mutualistic relationships, in terms of relative specialization of the partners, is important to understanding their ecology and evolution. Analyses of the mutualistic interaction between anemonefish and their host sea anemones show that the relationship is highly nested in structure, generalist species interacting with one another and specialist species interacting mainly with generalists. This supports the hypothesis that the configuration of mutualistic interactions will tend towards nestedness. In this case, the structure of the interaction is at a much larger scale than previously hypothesized, across more than 180 degrees of longitude and some 60 degrees of latitude, probably owing to the pelagic dispersal capabilities of these species in a marine environment. Additionally, we found weak support for the hypothesis that geographically widespread species should be more generalized in their interactions than species with small ranges. This study extends understanding of the structure of mutualistic relationships into previously unexplored taxonomic and physical realms, and suggests how nestedness analysis can be applied to the conservation of obligate species interactions.