Background: Shiga toxin-producing Escherichia coli (STEC) O157:H7 and O104:H4 strains are important causative agents of food-borne diseases such as hemorrhagic colitis and hemolytic–uremic syndrome, which is the leading cause of kidney failure and death in children under 5 years as well as in the elderly. Methods: the native E. coli O157:H7 and O104:H4 lipopolysaccharides (LPS) were partially deacylated under alkaline conditions to obtain apyrogenic S-LPS with domination of tri-acylated lipid A species—Ac3-S-LPS. Results: intraperitoneal immunization of BALB/c mice with Ac3-S-LPS antigens from E. coli O157:H7 and O104:H4 or combination thereof (di-vaccine) at single doses ranging from 25 to 250 µg induced high titers of serum O-specific IgG (mainly IgG1), protected animals against intraperitoneal challenge with lethal doses of homologous STEC strains (60–100% survival rate) and reduced the E. coli O157:H7 and O104:H4 intestinal colonization under an in vivo murine model (6–8-fold for monovalent Ac3-S-LPS and 10-fold for di-vaccine). Conclusions: Di-vaccine induced both systemic and intestinal anti-colonization immunity in mice simultaneously against two highly virulent human STEC strains. The possibility of creating a multivalent STEC vaccine based on safe Ac3-S-LPS seems to be especially promising due to a vast serotype diversity of pathogenic E. coli.