Staphylococcal enterotoxin B (SEB), produced by the gram-positive bacterium Staphylococcus aureus, is responsible for food poisoning and toxic shock syndrome, and is considered a potential bioterrorism agent. Unfortunately, still now no approved vaccines are available against SEB. In this study, we constructed a series of nontoxic SEB mutants (mSEBs) and examined whether these mSEBs provide protective immunity against SEB challenge. These mSEB vaccine candidates did not demonstrate superantigen activity in mouse splenocyte cultures. Immunization with the vaccine candidates triggered the production of IgG-antibodies with neutralizing activity. In addition, increased production of IgG1 and IgG3 was observed after immunization, which signifies both Th1- and Th2-induced immune responses. Among the vaccine candidates tested, S9, a double mutant (N23A and Y90A) and S19, a quadruple mutant (N23A, Y90A, R110A, and F177A), demonstrated complete protection against a lethal SEB challenge. Altogether, our results strongly suggest that these mSEBs could be an effective recombinant SEB vaccine candidates for further/future preclinical and clinical studies.