The purpose of this study was to evaluate Bacillus sp. SJ-10, isolated from traditional Korean seafood, as a probiotic. Strain SJ-10 was demonstrated to be safe, on the basis of in vitro tests confirming the absence of cytotoxicity, hemolysis, and genes with toxigenic potential, and was susceptible to antibiotics. It met the probiotic prerequisites of a spore count that remained almost constant, acid and bile tolerance under simulated gastrointestinal conditions, and significant adhesion to Caco-2 cells. Moreover, SJ-10 demonstrated beneficial properties as a probiotic: broad-spectrum antimicrobial activity, hydroxyl radical, antioxidant activity, production of functional enzymes such as β-galactosidase and phytase, and selective growth via β-glucan fermentation. The fish-feeding trial demonstrated that olive flounder fed diets containing SJ-10 alone or in combination with β-glucan exhibited significantly higher growth performance and pathogenic disease resistance compared with those fed diets containing β-glucan alone, indicating that SJ-10 diets exerted a beneficial effect as an antibiotic replacer in terms of growth performance and disease resistance in olive flounder.