The dynamics and prevalence of mutualistic interactions, which are responsible for the maintenance and structuring of all ecological communities, are vulnerable to changes in abiotic and biotic environmental conditions. Mutualistic outcomes can quickly shift from cooperation to conflict, but it unclear how resilient and stable mutualistic outcomes are to more variable conditions. Tidally controlled coral atoll lagoons that experience extreme diurnal environmental shifts thus provide a model from which to test plasticity in mutualistic behavior of dedicated (formerly obligate) cleaner fish, which acquire all their food resources through client interactions. Here we investigated cleaning patterns of a model cleaner fish species, the bluestreak wrasse (Labroides dimidiatus), in an isolated tidal lagoon on the Great Barrier Reef. Under tidally restricted conditions, uniquely both adults and juveniles were part-time facultative cleaners, pecking on Isopora palifera coral. The mutualism was not completely abandoned, with adults also wandering across the reef in search of clients, rather than waiting at fixed site cleaning stations, a behavior not yet observed at any other reef. Contrary to well established patterns for this cleaner, juveniles appeared to exploit the system, by biting (‘cheating’) their clients more frequently than adults. We show for the first time, that within this variable tidal environment, where mutualistic cleaning might not represent a stable food source, the prevalence and dynamics of this mutualism may be breaking down (through increased cheating and partial abandonment). Environmental variability could thus reduce the pervasiveness of mutualisms within our ecosystems, ultimately reducing the stability of the system.