Many client coral reef fishes have their ectoparasites removed by the cleaner wrasse Labroides dimidiatus in mutualistic interactions. Clients regularly receiving cleaning services reportedly benefit from increased growth and cognitive performance, but the underlying physiological changes that covary with such benefits are unknown. Here, we tested whether reduced access to cleaning services affects physiological state in two species of damselfish, Amblyglyphidodon curacao and Acanthochromis polyacanthus. We performed an in situ removal experiment on the Great Barrier Reef, Australia, whereby 47% of cleaners on a natural reef were removed. Since cleaners occupy defined territories (called cleaning stations), this removal created areas where small, resident clients, including A. polyacanthus and A. amblyglyphidodon, had no access to cleaning services. One month following cleaner removal, we measured body condition and collected blood samples from both damselfish species from territories with and without access to cleaners. Blood was used for estimating haematocrit levels, hormonal analyses, and immune cell counts. We tested for correlations among all these parameters to explore potential trade-offs in terms of growth, aerobic capacity, immune activation, and/or reproduction as a result of the loss of cleaning benefits. In both species, we found that fish without access to cleaners had lower haematocrit, testosterone levels, and lymphocyte counts than fish with access. There were no significant changes in fish body condition, leukocytes, granulocytes, or plasma cortisol levels between fish with access to cleaners or not. However, testosterone levels correlated negatively with the proportion of granulocytes in the blood of fish with access to cleaners. Our results suggest that even a relatively short-term reduction in access to cleaning services can have negative physiological outcomes for clients. Thus, the presence of cleaners on coral reefs appears to have important benefits for coral reef fish community health.