This study aimed to determine phylogenetic relationship between and among selected species of sea cucumbers (Echinodermata: Holothuroidea) using 16S mitochondrial ribosomal RNA (rRNA) gene. Phylogenetic analyses of 37 partial sequences of 16S mitochondrial rRNA gene using three main methods namely neighbour joining (NJ), maximum parsimony (MP) and maximum likelihood (ML) showed the presence of five main genera of sea cucumbers: Molpadia from order Molpadiida and four genera of order Aspidochirotida namely Holothuria, Stichopus, Bohadschia and Actinopyga. All of the 17 species obtained from Malaysia distributed among the main genera except within Actinopyga. Interestingly, Holothuria excellens was out of Holothuria group causing Holothuria to be paraphyletic. High bootstrap value and consistent clustering made Molpadia, Stichopus, Bohadschia and Actinopyga monophyletic. The relationship of Actinopyga with the other genera was unclarified and Stichopus was sister to Molpadia. The latter finding caused the resolution at order level unclear. The pairwise genetic distance calculated using Kimura 2-parameter model further supported and verified findings from the phylogenetic trees. Further studies with more samples and different mitochondrial DNA genes need to be done to get a better view and verification on the molecular phylogeny of sea cucumbers.