The cleaning of client fish by cleaner fish is one of the most highly developed interspecific communication systems known. But even though it is a seemingly obvious mutualism1,2, several quantitative studies3,5 have failed to show any benefit for the clients, leading to the hypothesis that cleaner fish are ‘behavioural parasites’ that exploit the sensory system of the clients6 to obtain food, rather than to increase the client's fitness. The cleaner fish Labroides dimidiatus eats parasitic gnathiid isopods, which decline in number on the client fish Hemigymnus melapterus daily between dawn and sunset7,8. I find that the cleaner fish reduces parasite abundance, resulting in a 4.5-fold difference within 12 hours, supporting the hypothesis that cleaning behaviour is mutualistic.