Gastrointestinal disease caused by Shiga toxin-producing bacteria (such as Escherichia coli O157:H7 and Shigella dysenteriae) is often complicated by life-threatening toxin-induced systemic sequelae, including hemolytic-uremic syndrome. Such infections can now be diagnosed very early in the course of the disease, but at present no effective therapeutic intervention is possible. Here, we constructed a recombinant bacterium that displayed a Shiga toxin receptor mimic on its surface, and it adsorbed and neutralized Shiga toxins with very high efficiency. Moreover, oral administration of the recombinant bacterium completely protected mice from challenge with an otherwise 100%-fatal dose of Shiga toxigenic E. coli. Thus, the bacterium shows great promise as a 'probiotic' treatment for Shiga toxigenic E. coli infections and dysentery.