The preferences exhibited by cleaner fishes for particular client species and the high variability in rates at which various clients visit cleaning stations have remained largely unexplained. In this study, we assessed the relative importance of client ectoparasite load and mucus characteristics for the behaviour of cleaning gobies, Elacatinus spp, and their fish clients on a Barbadian fringing reef. Client species with high ectoparasite loads visited cleaning stations more often than less parasitised species. This effect was independent of body size. Frequency of visits to cleaning stations was not related to client mucus characteristics. These results suggest that the main motivation for clients to interact with cleaners is ectoparasite removal. Cleaners did not preferentially clean clients with higher ectoparasite load or better mucus, nor did they spend more time inspecting such clients. The interests of cleaners and clients therefore appear to be inconsistent. This may be due to the generally low rate of ectoparasitism on Barbadian fish compared to fish of other regions. Cleaning gobies fed at a lower rate on client species with higher loads of gnathiid isopod larvae, which may be explained if cleaners switch from eating ectoparasites to other items, such as mucus, on clients with few ectoparasites. Our estimates of caloric and protein content of fish mucus suggest that it may be as valuable a food source per unit weight as ectoparasites. However, no data are available to compare the value of each item per unit feeding time. The fact that clients with few ectoparasites still visit cleaners, albeit at a low rate, suggests that the cost of mucus removal may be low, compared to the benefit of incidental parasite removal. Thus, the outcome of cleaning interactions may remain positive, even in areas characterised by naturally low parasitism on clients.