The microbiome provides resistance to infection. However, the underlying mechanisms are poorly understood. We demonstrate that colonization with the intestinal bacterium Clostridium scindens protects from Entamoeba histolytica colitis via innate immunity. Introduction of C. scindens into the gut microbiota epigenetically altered and expanded bone marrow granulocyte-monocyte progenitors (GMPs) and resulted in increased intestinal neutrophils with subsequent challenge with E. histolytica. Introduction of C. scindens alone was sufficient to expand GMPs in gnotobiotic mice. Adoptive transfer of bone marrow from C. scindens-colonized mice into naive mice protected against amebic colitis and increased intestinal neutrophils. Children without E. histolytica diarrhea also had a higher abundance of Lachnoclostridia. Lachnoclostridia C. scindens can metabolize the bile salt cholate, so we measured deoxycholate and discovered that it was increased in the sera of C. scindens-colonized specific pathogen-free and gnotobiotic mice, as well as in children protected from amebiasis. Administration of deoxycholate alone increased GMPs and provided protection from amebiasis. We elucidated a mechanism by which C. scindens and the microbially metabolized bile salt deoxycholic acid alter hematopoietic precursors and provide innate protection from later infection with E. histolytica.