In a given area, plant-animal mutualistic interactions form complex networks that often display nestedness, a particular type of asymmetry in interactions. Simple ecological and evolutionary factors have been hypothesized to lead to nested networks. Therefore, nestedness is expected to occur in other types of mutualisms as well. We tested the above prediction with the network structure of interactions in cleaning symbiosis at three reef assemblages. In this type of interaction, shrimps and fishes forage on ectoparasites and injured tissues from the body surface of fish species. Cleaning networks show strong patterns of nestedness. In fact, after controlling for species richness, cleaning networks are even more nested than plant-animal mutualisms. Our results support the notion that mutualisms evolve to a predictable community-level structure, be it in terrestrial or marine communities.