Cleaner shrimp and their reef fish clients are an interspecific mutualistic interaction that is thought to be mediated by signals, and a useful system for studying the dynamics of interspecific signalling. To demonstrate signalling, one must show that purported signals at minimum (a) result in a consistent state change in the receiver and (b) contain reliable information about the sender’s intrinsic state or future behaviour. Additionally, signals must be perceptible by receivers. Here, we document fundamental attributes of the signalling system between the cleaner shrimp Ancylomenes pedersoni and its clients. First, we use sequential analysis of in situ behavioural interactions to show that cleaner antenna whipping reliably predicts subsequent cleaning. If shrimp do not signal via antenna whipping, clients triple their likelihood of being cleaned by adopting darker colouration over a matter of seconds, consistent with dark colour change signalling that clients want cleaning. Using experimental manipulations, we found that visual stimuli are sufficient to elicit antenna whipping, and that shrimp are more likely to “clean” dark than light visual stimuli. Lastly, we show that antenna whipping and colour change are perceptible when accounting for the intended receiver’s visual acuity and spectral sensitivity, which differ markedly between cleaners and clients. Our results show that signalling by both cleaners and clients can initiate and mediate their mutualistic interaction.