Symbiosis often occurs between partners with distinct life history characteristics and dispersal mechanisms. Many bacterial symbionts have genomes comprised of multiple replicons with distinct rates of evolution and horizontal transmission. Such differences might drive differences in population 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 Sinorhizobium meliloti collected from 21 locations in southern Europe to characterize population structures of this bacterial symbiont and its host plant Medicago truncatula. Sinorhizobium 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 among-replicon differences in the extent of horizontal gene transfer, although given limited recombination of the chromosome, different levels of purifying or positive selection may also contribute to among-replicon differences. 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 local specialization.