Symbiosis often occurs between partners with distinct life history characteristics and dispersal mechanisms. Bacterial symbionts often have genomes comprised of multiple replicons with distinct rates of evolution and horizontal transmission. Such differences might drive differences in population genetic structure between hosts and symbionts and among the elements of the divided genomes of bacterial symbionts. These differences might, in turn, shape the evolution of symbiotic interactions and bacterial evolution. Here we use whole genome resequencing of a hierarchically-structured sample of 191 strains of Ensifer meliloti collected from 21 locations in the native range to characterize population structure of this bacterial symbiont and its host plant Medicago truncatula. E. meliloti genomes showed high local (within-site) variation and little isolation by distance. This was particularly true for the two symbiosis elements pSymA and pSymB, which have population structures that are similar to each other, but distinct from both the bacterial chromosome and the host plant. The differences in population structure may result from differences in mobility or selection driving bacterial adaptation to life in the soil versus in association with plants. Discordant population structure between hosts and symbionts indicates that geographically and genetically distinct host populations in different parts of the range might interact with genetically similar symbionts, potentially minimizing the potential for local specialization.