In this study, Bacillus licheniformis which has been used as probiotics was isolated from Korean traditional fermented soybean. A total of 69 strains were presumptively identified as B. licheniformis by phenotypic methods. Based on PCR amplification and 16S rRNA gene sequencing, the multilocus sequence typing of gyrA and rpoB, followed by phylogenetic analysis was performed. The isolates were distinctly differentiated and found to be closely related to B. amyloliquefaciens, B. subtilis, and B. aerius. The partial 16S rRNA gene sequences of those strains matched those of B. sonorensis (97%) and B. aerius (98%) in the phylogenetic tree. In contrast, multilocus phylogenetic analysis (MLPA) showed that only 61 (86.9%) out of 69 strains were B. licheniformis. The rest of those strains were found to be B. subtilis (5.8%), B. amyloliquefaciens (2.9%), and B. sonorensis (2.9%), respectively. Therefore, our results suggested that since the 16S rRNA gene sequencing alone was not sufficient to compare and discriminate closely related lineages of Bacillus spp., it was required to analyze the MLPA simultaneously to avoid any misleading phenotype-based grouping of these closely related species.