This study aimed to resolve the taxonomic status of a morphologically undetermined sea cucumber species of order Apodida from Malaysia (GenBank accession no.: FJ223867) using partial 16S mitochondrial rRNA gene sequences and subsequently to determine the validity of morphological taxonomy of Holothuria species into its current subgenera. The undetermined species clustered with all taxa of Holothuria in previous study. Phylogenetic analyses using maximum parsimony and Bayesian methods suggest that the undetermined species was genetically closer to Holothuria (Lessonothuria) pardalis and Holothuria (Acanthotrapeza) coluber; and its position in both phylogenetic trees further suggests its status as a Holothuria taxon. Subgenera of Holothuria, Merthensiothuria and Metriatyla are monophyletic with strong bootstrap supports and posterior probabilities of clades, thus strengthening their morphological taxonomies. Nonetheless, the non-monophyly of subgenera of Halodeima, Microthele and Platyperona suggests a requirement for their taxonomic revisions using integrative taxonomy. The status of Holothuria (Halodeima) edulis subgroups in the maximum parsimony and Bayesian trees is indistinct and further taxonomic revisions are necessary. In terms of sister relationship, both phylogenetic trees suggest that subgenus Holothuria is a sister taxon of subgenus Roweothuria while the other sister relationships were unclear due to the undetermined species, paraphyly and polyphyly of a number of subgenera. Further studies with more specimens of genus Holothuria from broader geographical locations and various mtDNA genes along with morphological approaches may facilitate to provide better insights into the molecular phylogeny of subgenera of Holothuria.