The Gram-negative bacterium, Legionella pneumophila, is a protozoan parasite and accidental intracellular pathogen of humans. We propose a model in which host cycling through multiple protozoan hosts in the environment holds L. pneumophila in a state of evolutionary stasis as a broad host-range pathogen. Using an experimental evolution approach, we tested this hypothesis by restricting L. pneumophila to growth within mouse macrophages for hundreds of generations. Whole-genome resequencing and high-throughput genotyping identified several parallel adaptive mutations and population dynamics that led to improved replication within macrophages. Based on these results, we provide a detailed view of the population dynamics of an experimentally evolving bacterial population, punctuated by frequent instances of transient clonal interference and selective sweeps. Non-synonymous point mutations in the flagellar regulator, fleN, resulted in increased uptake and broadly increased replication in both macrophages and amoebae. Mutations in multiple steps of the lysine biosynthesis pathway were also independently isolated, resulting in lysine auxotrophy and reduced replication in amoebae. These results demonstrate that under laboratory conditions, host restriction is sufficient to rapidly modify L. pneumophila fitness and host range. We hypothesize that, in the environment, host cycling prevents L. pneumophila host-specialization by maintaining pathways that are deleterious for growth in macrophages and other hosts.