A few studies on the presence of microbes and their association in sea cucumbers can be found to date, especially in Apostichopus japonicus. However, such studies on Malaysian sea cucumbers and in the gastrointestines of the echinoderms are still lacking. Therefore, the aims of this study are to isolate and identify associated bacteria in the gastrointestines of two common species of Malaysian sea cucumbers i.e. Holothuria (Mertensiothuria) leucospilota (Brandt, 1835), the most dominant sea cucumber species in Malaysia, and Stichopus horrens Selenka, 1867, the commercial gamat species. A number of six genera of Gram-positive bacteria representing the order Bacillales and the order Micrococcales i.e. Bacillus, Brevibacillus, Lysinibacillus, Staphylococcus, Dermacoccus and Micrococcus are isolated from the gastrointestines of H. leucospilota, as suggested by the phylogenetic trees of partial 16S rRNA gene sequences. Meanwhile, three genera of Gram-positive bacteria that represent the order Bacillales i.e. Bacillus, Brevibacillus and Lysinibacillus are isolated from the gastrointestines of S. horrens. Interestingly, 60% of the bacterial species have been known to contain commercial potentials mainly as antibiotic producers, and only bacteria with commercial potentials were present in the gastrointestines of S. horrens. In contrast to that, bacteria that could be pathogenic were also present in the gastrointestines of H. leucospilota. The presence of all bacteria that have been known to contain commercial potentials in the gastrointestines of S. horrens and more diverse microbial population in H. leucospilota could be due to the higher level of antimicrobial properties in the gastrointestines of S. horrens. However, experiments on antibacterial properties of the isolates have to be done and those proven to contain commercial potential can be exploited towards the development of industrial applications in Malaysia.