Partner choice is likely to be an important mechanism for the maintenance of cooperation in many mutualisms, and cleaner mutualisms among fish have been a model system for testing predictions of partner choice theories. Fish seeking to be cleaned ( clients) face two potential problems: cleaners may cheat them by feeding on tissue or mucous, and they may have to wait for service from a cleaner. Previous work on interactions between the bluestreak cleaner wrasse, Labroides dimidiatus, and its clients indicates that cleaners provide higher-quality service to species that have the option of switching partners. These results have been interpreted as evidence that partner choice leads cleaners to behave cooperatively; however, alternative explanations exist for these between-species patterns. Here I focus on interactions between the bluestreak cleaner wrasse and a single client species that varies in its ability to switch partners to test the prediction that clients receive higher-quality service when cleaners have to compete for access to them. The results indicate that cleaners give ornate butterflyfish, Chaetodon ornatissimus, priority of access to their services when these clients can switch partners; however, ornate butterflyfish are not cheated less often when they have access to multiple cleaner stations, and they frequently respond to cheating by aggressively chasing cleaners. In combination with previous work, these results indicate that partner choice influences cooperative interactions between bluestreak cleaner wrasse and their clients, but that some clients with the ability to switch partners may use other strategies (i.e. punishment) to limit cheating by cleaners. (C) 2010 The Association for the Study of Animal Behaviour. Published by Elsevier Ltd. All rights reserved.