Most studies and records of cleaning symbiosis between reef fish originate from shallow waters, ranging about 1–30 m depth. We record herein the wrasse Bodianus pulchellus and the goby Elacatinus phthirophagus cleaning below 60 m depth in the tropical south-western Atlantic. The wrasse was recorded cleaning two large piscivorous clients (a jack and a grouper) and the goby was recorded cleaning a grouper. Cleaning interactions between deep-reef fish and both of these cleaners may be expected at depths even greater than those reported here.