It is currently widely accepted that the complexity of a species’ social life is a major determinant of its brain complexity, as predicted by the social brain hypothesis. However, it remains a challenge to explain what social complexity exactly is and what the best corresponding measures of brain anatomy are. Absolute and relative size of the brain and of the neocortex have often been used as a proxy to predict cognitive performance. Here, we apply the logic of the social brain hypothesis to marine cleaning mutualism involving the genus Labroides. These wrasses remove ectoparasites from ‘client’ reef fish. Conflict occurs as wrasse prefer client mucus over ectoparasites, where mucus feeding constitutes cheating. As a result of this conflict, cleaner wrasse show remarkable Machiavellian-like behaviour. Using own data as well as available data from the literature, we investigated whether the general brain anatomy of Labroides provides any indication that their Machiavellian behaviour is associated with a more complex brain. Neither data set provided evidence for an increased encephalisation index compared to other wrasse species. Published data on relative sizes of brain parts in 25 species of the order Perciformes suggests that only the diencephalon is relatively enlarged in Labroides dimidiatus. This part contains various nuclei of the social decision making network. In conclusion, gross brain anatomy yields little evidence for the hypothesis that strategic behaviour in cleaning selects for larger brains, while future research should focus on more detailed aspects like the sizes of specific nuclei as well as their cryoarchitectonic structure and connectivity.