Interspecific mutualisms are an essential feature of life on earth, yet we know little about their evolution and stability. In many mutualisms several species are available as partners, raising questions about the similarity in function and behavioural repertoire depending on the partner species. Furthermore, variation between species in the quantity and quality of interactions resulting in variation in payoffs may allow us to infer the potential evolutionary origin of a multispecies mutualism complex. We addressed these issues in the marine cleaning mutualism, in which so-called 'cleaners' remove ectoparasites from so-called 'client' reef fish. We measured several parameters concerning the quantity and quality of cleaning interactions in six sympatric cleaner wrasse species. We found significant variation between cleaner species with respect to client diversity, the number of interactions with predatory clients, the duration of interactions, the frequency of client jolts as a correlate of 'cheating' by cleaners, and behaviours used for manipulation of client decisions. Exploratory correlations between cleaner species' dependency and our variables of interest suggest that cleaning originated as a conflict-free by-product mutualism and evolved towards more sophisticated behaviours, including strategic behaviours for interactions with predators, cheating and manipulation specifically adapted to the client type.