The yellowcheek wrasse Halichoeres cyanocephalus (Bloch) is registered by the first time for the Colombian Caribbean. In spite of extensive diving in most reef areas of Colombia since 1980, H. cyanocephalus was observed only in four occasions at the Tayrona Natural Park, the Urabá area, and San Andrés island. The fish is known to occur in deep waters but in Colombia it was found only in shallow (7-15 m in depth) reef environments. Eight species of the genus Halichoeres are now known from the Colombian Caribbean.