Bacteria evolve by mutation accumulation in laboratory experiments, but tempo and mode of evolution in natural environments are largely unknown. Here, we study the ubiquitous natural process of host colonization by commensal bacteria. We show, by experimental evolution of Escherichia coli in the mouse intestine, that the ecology of the gut controls the pace and mode of evolution of a new invading bacterial strain. If a resident E. coli strain is present in the gut, the invading strain evolves by rapid horizontal gene transfer (HGT), which precedes and outweighs evolution by accumulation of mutations. HGT is driven by 2 bacteriophages carried by the resident strain, which cause an epidemic phage infection of the invader. These dynamics are followed by subsequent evolution by clonal interference of genetically diverse lineages of phage-carrying (lysogenic) bacteria. We show that the genes uptaken by HGT enhance the metabolism of specific gut carbon sources and provide a fitness advantage to lysogenic invader lineages. A minimal dynamical model explains the temporal pattern of phage epidemics and the complex evolutionary outcome of phage-mediated selection. We conclude that phage-driven HGT is a key eco-evolutionary driving force of gut colonization—it accelerates evolution and promotes genetic diversity of commensal bacteria.