Several obligate associate crabs and shrimps species may co-occur and interact within a single coral host, leading to patterns of associations that can provide essential ecological services. However, knowledge of the dynamics of interactions in this system is limited, partly because identifying species involved in the network remains challenging. In this study, we assessed the diversity of the decapods involved in exosymbiotic assemblages for juvenile and adult Pocillopora damicornis types ? and ? on reefs of New Caledonia and Reunion Island. This approach revealed complex patterns of association at regional and local scales with a prevalence of assemblages involving crab-shrimp partnerships. Furthermore, the distinction of two lineages in the snapping shrimp Alpheus lottini complex, rarely recognized in ecological studies, reveals a key role for cryptic diversity in structuring communities of mutualists. The existence of partnerships between species that occurred more commonly than expected by chance suggests an increased advantage for the host or a better adaptation of associated species to local environmental conditions. The consideration of cryptic diversity helps to accurately describe the complexity of interaction webs for diverse systems such as coral reefs, as well as the functional roles of dominant associated species for the persistence of coral populations.