Cleaning interactions, which involve a cleaner
removing ectoparasites and other material from the body of a heterospecific (client), are iconic symbiotic interactions observed on coral reefs worldwide. These small cleaners play a disproportionately large role in the structuring and function of coral reefs, influencing species interaction networks, client health and biodiversity. Cleaning patterns, however, are likely to be context-dependent and highly heterogeneous, and although we have some understanding about their spatial variation, longer-term temporal changes in cleaning interactions have remained understudied. Given that coral reefs are globally threatened and are currently experiencing large shifts in their biodiversity, it is vital that we determine which clients are consistently most important for maintaining cleaning. Using a long-term, 8-yr data set (2010–17) on the cleaning behaviour of the predominant Caribbean cleaner, the sharknose goby (Elacatinus evely-nae), we investigated whether cleaner fish from the same reef show consistent patterns in their interactions with client species over time. Here we conclusively show that cleaning behaviour is highly plastic, as no single species or family was cleaned consistently more than others, in terms of cleaning frequency and duration, across all years. Only 40% of the species were cleaned more than others, and we also observed ca. one-third of species experience inconsistent cleaning patterns across years. Our study thus quantifies how dynamic cleaner–client relationships are on the same reef across years and highlights the importance of long-term data.