Plotosus canius (Hamilton, 1822) is a significant marine species in Malaysia from nutritional and commercial perspectives. Despite numerous fundamental research on biological characteristics of P. canius, there are various concerns on the level of population differentiation, genomic structure, and the level of genetic variability among their populations due to deficiency of genetic-based studies. Deficiency on basic contexts such as stock identification, phylogenetic relationship and population genetic structure would negatively impact their sustainable conservation. Hence, this study was conducted to characterize the genetic structure of P. canius for the first time through the application of mitochondrial Cytochrome Oxidase I (COI) gene, cross amplification of Tandanus tandanus microsatellites, and a total of 117 collected specimens across five selected populations of Malaysia. The experimental results of the mitochondrial analysis revealed that the haplotype diversity and nucleotide diversity varied from 0.395–0.771 and 0.033–0.65 respectively. Moreover, the statistical analysis of microsatellites addressed a considerable heterozygote insufficiency in all populations, with average observed heterozygosity ( H o ) value of 0.2168, which was lower than the standard heterozygosity in marine populations ( H o = 0.79). This alongside the high Fis values estimation, high pairwise differentiation among populations and low within population variations are supposed to be associated with small sample size, and inbreeding system. Besides, the significant finding of this study was the sharing of common haplotype KR086940, which reflects a historical genetic connectivity between Peninsular Malaysia and Borneo populations due to the geological history of Southeast Asia during Pleistocene era. Demographic analyses showed that all populations were in an equilibrium state with no significant evidence of population expansion. To put it briefly, the current study has managed to provide an initial genomic database toward understanding of the genetic characterization, phylogenetic, molecular diversification and population structure in P. canius, and should be necessary highlighted for appropriate management and conservation of species. Further studies must be carried out involving more geographical and sampling sites, larger population size per site, and utilization of species specific microsatellites loci.