Humans are highly social animals and often help unrelated individuals that may never reciprocate the altruist's favour(1-5). This apparent evolutionary puzzle may be explained by the altruist's gain in social image: image-scoring bystanders, also known as eavesdroppers, notice the altruistic act and therefore are more likely to help the altruist in the future(5-7). Such complex indirect reciprocity based on altruistic acts may evolve only after simple indirect reciprocity has been established, which requires two steps. First, image scoring evolves when bystanders gain personal benefits from information gathered, for example, by finding cooperative partners(8-10). Second, altruistic behaviour in the presence of such bystanders may evolve if altruists benefit from access to the bystanders. Here, we provide experimental evidence for both of the requirements in a cleaning mutualism involving the cleaner fish Labroides dimidiatus. These cleaners may cooperate and remove ectoparasites from clients or they may cheat by feeding on client mucus(11,12). As mucus may be preferred over typical client ectoparasites(13), clients must make cleaners feed against their preference to obtain a cooperative service. We found that eavesdropping clients spent more time next to 'cooperative' than 'unknown cooperative level' cleaners, which shows that clients engage in image-scoring behaviour. Furthermore, trained cleaners learned to feed more cooperatively when in an `image-scoring' than in a 'non-image-scoring' situation.