This study aimed at documenting species richness and distribution of sea cucumbers (Phylum Echinodermata: Class Holothuroidea) in Malaysia. Sea cucumber collections were conducted from August 2004 until November 2011 from several study sites in Peninsular Malaysia and Sabah. A total of fifty two morphospecies of sea cucumbers from four orders comprising of 12 genera were documented. Thirty eight species were recorded for Sabah, followed by 24 species for Peninsular Malaysia, and 10 species were recorded in both regions. However, nine species required further taxonomic works for their identification. Of the 15 Actinopyga species recorded, 14 species were from Sabah and one species was from Peninsular Malaysia. The order Aspidochirotida in general, and genus Holothuria in particular were the dominant taxa. Holothuria (Mertensiothuria) leucospilota (Brandt, 1835) is the dominant species in Malaysia as it was observed and documented at all collection sites. Future studies on the species richness of sea cucumbers are required in Sarawak marine waters and the molecular phylogeny of the sea cucumbers in order to obtain a better understanding of the evolutionary relationships between the sea cucumbers of Malaysia.