Measuring selection acting on microbial populations in natural or even semi-natural environments is challenging because many microbial populations experience variable selection. The majority of rhizobial bacteria are found in the soil. However, they also live symbiotically inside nodules of legume hosts and each nodule can release thousands of daughter cells back into the soil. We tested how past selection (i.e., legacies) by two plant genotypes and by the soil alone, affected selection and genetic diversity within a population of 101 strains of Ensifer meliloti. We also identified allelic variants most strongly associated with soil- and host-dependent fitness. In addition to imposing direct selection on rhizobia populations, soil and host environments had lasting effects across host generations. Host presence and genotype during the legacy period explained respectively 22% and 12% of the variance in the strain composition of nodule communities in the second cohort. While strains with high host fitness in the legacy cohort tended to be enriched in the second cohort, the diversity of the strain community was greater when the second cohort was preceded by host rather than soil legacies. Our results indicate the potential importance of soil selection driving the evolution of these plant-associated microbes.