Infections by multidrug-resistant Enterobacteriaceae (MRE) are life-threatening to patients. The intestinal microbiome protects against MRE colonization, but antibiotics cause collateral damage to commensals and open the way to colonization and subsequent infection. Despite the significance of this problem, the specific commensals and mechanisms that restrict MRE colonization remain largely unknown. Here, by performing a multi-omic prospective study of hospitalized patients combined with mice experiments, we find that Lactobacillus is key, though not sufficient, to restrict MRE gut colonization. Lactobacillus rhamnosus and murinus increase the levels of Clostridiales bacteria, which induces a hostile environment for MRE growth through increased butyrate levels and reduced nutrient sources. This mechanism of colonization resistance, an interaction between Lactobacillus spp. and Clostridiales involving cooperation between microbiota members, is conserved in mice and patients. These results stress the importance of exploiting microbiome interactions for developing effective probiotics that prevent infections in hospitalized patients.