Cleaner fishes remove and consume ectoparasites and are often categorized by whether they perform this behavior: 1) predominately as juveniles, 2) facultatively throughout ontogeny, or 3) obligately. Through a literature search, we confirmed that with at least 58 species exhibiting cleaning behavior, the Labridae (wrasses, parrotfishes, and allies) contain the highest diversity of cleaner fishes. In fact, there are 3-4 times as many cleaners within labrids as there are in any other marine group. The distribution and underlying causes of this exceptional diversity have not been determined. Here, we assess the topological and temporal patterns of labrid cleaner evolution. We used maximum likelihood and Bayesian approaches to infer the phylogenetic relationships and divergence times between 320 labrid species (50.7% of nominal species). We then employed stochastic character mapping to infer how and when cleaning behavior evolved. We estimate that cleaning has independently evolved 26-30 times in the Labridae, and all such events likely occurred no earlier than in the late Miocene. Given the current sampling and pattern of transitions, we hypothesize that the majority of facultative or obligate cleaning may have evolved through heterochrony.