Gobiosoma evelynae (Böhlke and Robins), G. prochilos (Böhlke and Robins), and juvenile Thalassoma bifasciatum (Bloch), long known to be ectoparasite-pickers, are differentiated in terms of their associations with the fishes they clean. The gobies are found to have very broad cleaning preferences, while the wrasse largely restricts its cleaning to non-piscivores. The protection from predation of the gobies is attributed to a more highly evolved specialization as a cleaner than that found in the wrasse. Tank experiments show piscivores to prey readily upon the wrasse, while the gobies exhibit cleaning behavior recognized by the piscivores, and thus escape predation.