Gut microbial DNA is known as our “other genome”, yet little is known about how it evolves over time. We developed a model-based framework for quantifying evolutionary dynamics within and across hosts using shotgun or read-cloud metagenomic data. Within hosts, we find that on time scales less than a year, invasions of distantly related strains are rare. Instead, we more commonly observe evolutionary changes in resident strains. By comparing these mutations with typical between-host differences, we find evidence that some sweeps are seeded by cross-strain recombination rather than new mutations. In contrast, our analysis of adult twins suggests that invasion eventually comes to dominate on long time scales. To elucidate specific genes associated with the ability to colonize the human gut, we developed metagenomic sequencing based estimators of the propensity of a species for the gut environment and associated these statistics with gene presence across the bacterial tree of life with phylogenetic regression. We conclude that specific genes increase the probability a species thrives in the human gut, but bacteria are limited in their ability to become hyper-adapted to their host.