Sea cucumbers (Holothuroidea) are important in Malaysia due to their diversity and commercial value. The sequencing of a 465 base pair (bp) region of the 16S rRNA was utilized to characterize and identify sea cucumbers from the northern region of the Straits of Malacca. The objective of this study was to infer the phylogenetic relationship of the different species collected, based on the DNA sequencing of the mitochondrial 16S rRNA gene. In all 21 samples were extracted, analysed and sequenced for this gene. The sequences were aligned and edited using MEGA 4, followed by the construction of neighbour-joining and maximum parsimony trees. Three genera were identified: namely Holothuria and Stichopus from the order Aspidochirotida, and the genus Molpadia from the order Molpadia. Polymerase Chain Reaction (PCR) gave the desired products of the amplified 16s rRNA mtDNA region with lengths of approximately 525 bp. Multiple aligned partial sequences of 16s rRNA mtDNA ranging from 464 bp to 465 bp were utilized for further analyses. Twenty one ingroups of sea cucumbers and one outgroup represented by Mespilia globulus were included in the construction of neighbour-joining (NJ) and maximum parsimony (MP) phylogenetic trees. Further studies are required to clarify the taxonomic status of this group using other molecular markers with additional samples from other sites.