The potential probiotic of a total of 15 Bacillus species isolated from Korean soybean paste (doenjang) was evaluated. Among those tested, the CSY191 and CSY388 strains were selected as probiotic bacteria due to their acid and bile tolerance, respectively. These strains were classified as Bacillus subtilis based on morphological, physiological, and chemotaxonomic features as well as on phylogenetic analysis based on their 16S rDNA sequences. These strains CSY191 and CSY388 showed a significant survival with rate range of 30.0 to 58.3% and of 31.0% to 58.1%, respectively, under artificial gastric acidic conditions at pH 3.0. These CSY191 and CSY388 strains appeared to have high antimicrobial activity against Salmonella Typhimurium, Bacillus cereus and Listeria monocytogenes. Also, methanol extractions (surfactin-like compounds) of strain CSY191 and strain CSY388 activated RAW264.7 microphages and induced the production of nitric oxide (NO) in a concentration-dependent manner, respectively. Therefore, strain CSY191 and strain CSY388 can be used as potential probiotics.