The present study describes the cleaning interactions among species of cleaner gobies Tigrigobius spp. and Elacatinus puncticulatus (family Gobiidae) and the client fish species they clean in a coral reef of Gorgona Island, Colombia. In 419 cleaning events, we observed 27 species acting as clients of Tigrigobius spp., whereas only nine were clients of E. puncticulatus. Paranthias colonus and Cephalopholis panamensis were the species most commonly cleaned by Tigrigobius spp., while Ophioblennius steindachneri and Stegastes acalpulcoensis were the clients most commonly cleaned by E. puncticulatus. The abundance (but not the body size) of clients was an important variable predicting the cleaning frequency observed for clients of Tigrigobius spp., but this was not the case for clients of E. puncticulatus. Additionally, Tigrigobius spp. preferred cleaning planktivores, sessile invertebrate feeders and territorial herbivores (Ivlev's index >0·15), whereas E. puncticulatus did not exhibit any preference. We observed two major peaks of cleaning activity for Tigrigobius spp., one in the early morning and another one in the late afternoon. These results suggest that Tigrigobius spp. is a specialized cleaner goby, whereas E. puncticulatus is a facultative cleaner that cleans sporadically.