Bacillus sp. SJ-10 (KCCM 90078, JCM 15709) is a halotolerant bacterium isolated from a traditional Korean food, i.e., salt-fermented fish (jeotgal). The bacterium can survive and engage in metabolism at high salt concentrations. Here, we reported complete genome sequence of Bacillus sp. SJ-10, which has a single circular chromosome of 4,041,649 base pairs with a guanine-cytosine content of 46.39%. Bacillus sp. SJ-10 encodes a subunit of poly-gamma-glutamic acid (gamma-PGA) with a molecular weight of approximately 400 kDa, which contains four gamma-PGA synthases (pgsB, pgsC, pgsAA and pgsE) and one gamma-PGA-releasing gene (pgsS). This bacterium also able to produce salt-stable enzymes such as protease, beta-glucosidase, and beta-1,3-1,4-glucanase. This affords significant insights into strategies employed by halotolerant bacteria to survive at high salt concentrations. The sequence contains information on secondary metabolites biosynthetic gene cluster, and most importantly enzymes produced by the bacterium may be valuable with respect to food, beverage, detergent, animal feed, and certain commercial contexts.