Sea cucumber (bêche-de-mer, Echinodermata: Holothuroidea) is one of the top internationally traded seafood varieties. Besides its direct nutritional benefits, it is continuously used in the traditional medicine in different areas and cultures in the world. This world-wide interest triggered various issues related to stocks´ declining and risks of species extinction. For these reasons, the current study was designed to provide molecular tools for accurate discrimination between two sea cucumber species that prevail the Mediterranean of these echinoderms in Egypt, that are Holothuria polii and H. sanctori. The power of three gene markers, i.e., 16S rDNA, 28S rDNA, and Histone H3 in achieving accurate DNA-based identification, as well as elucidating clear phylogenetic and genetic diversity differences between those two species was assessed. Among the three genes, 16S rDNA showed the highest potentials as genetic and phylogenetic species discrimination marker. Both 28S rDNA and H3 exhibited the least number of holothuroid reference sequences in the GenBank database. For genetic diversity within each species population, 16S rDNA exhibited the best potentials, followed by H3. 28S rDNA showed no genetic polymorphism at all. Moreover, the collective data of both H3 and 16S rDNA suggested a possible role of asexual reproduction behavior in H. sanctori in the reduction of genetic diversity, as a possible response to overfishing. Hence, the current research can recommend the simultaneous application of both 16S rDNA and H3 as accurate markers for genetic discrimination among H. polii, H. sanctori and other different holothuroid species.