Yersiniosis belongs to the common foodborne diseases around the world, and frequently manifests as diarrhea that can be treated with probiotics. Colicin F-Y is an antibacterial agent produced by bacteria and it is capable of specific growth inhibition of Yersinia enterocolitica, the causative agent of gastrointestinal yersiniosis. In this study, recombinant E. coli producing colicin F-Y were constructed, using both known probiotic strains EcH22 and EcColinfant, and the newly isolated murine strains Ec1127 and Ec1145. All E. coli strains producing colicin FY inhibited growth of pathogenic Y. enterocolitica during co-cultivation in vitro. In dysbiotic mice treated with streptomycin, E. coli strains producing colicin F-Y inhibited progression of Y. enterocolitica infections. This growth inhibition was not observed in mice with normal gut microflora, likely due to insufficient colonization capacity of E. coli strains and/or due to spatial differences in intestinal niches. Isogenic Y. enterocolitica producing colicin F-Y was constructed and shown to inhibit pathogenic Y. enterocolitica in mice with normal microflora. Evidence of in vivo antimicrobial activity of colicin F-Y may have utility in the treatment of Y. enterocolitica infections.