The Cheilostomes are the most diverse existent bryozoans group. Its species are commonly found in all the marine ecosystems around the world. In Colombia, however, information about them is scarce and limited to few localities. With the initiative of exploring the soft bottom biodiversity and completing the Colombian marine fauna inventories, INVEMAR-Macrofauna II exploration took place in March 2001, during which samples were collected on soft bottoms throughout the Colombian Caribbean from the continental shelf and the upper slope (20 – 500 m depth) by trawling. 62 species of Cheilostomes that belong to 39 families were found, 36 are first records for the Colombian Caribbean, 4 for the Great Caribbean and 1 for the Tropical West Atlantic. Bathymetric and geographic ranges are extended for 13 species. Taxonomical notes and images of the five species that are first records for the Greater Caribbean and the Tropical West Atlantic are included in this survey. It also includes remarks about the distribution, substrata, and growth types of Cheilostomata studied.