In root-nodule symbioses (RNS) between nitrogen (N) fixing bacteria and plants, bacterial symbionts cycle between nodule-inhabiting and soil-inhabiting niches that exert differential selection pressures on bacterial traits. Little is known about how the resulting evolutionary tension between host plants and symbiotic bacteria structures naturally occurring bacterial assemblages in soils. We used DNA cloning to examine soil-dwelling assemblages of the actinorhizal symbiont Frankia in sites with long-term stable assemblages in Alnus incana ssp. tenuifolia nodules. We compared: 1) phylogenetic diversity of Frankia in soil vs. nodules, 2) change in Frankia assemblages in soil vs. nodules in response to environmental variation: both across succession, and in response to long-term fertilization with N and phosphorus, and 3) soil assemblages in the presence and absence of host plants. Phylogenetic diversity was much greater in soil-dwelling than nodule-dwelling assemblages, and fell into two large clades not previously observed. Presence of host plants was associated with enhanced representation of genotypes specific to A. tenuifolia, and decreased representation of genotypes specific to a second Alnus species. The relative proportion of symbiotic sequence groups across a primary chronosequence was similar in both soil and nodule assemblages. Contrary to expectations, both N and P enhanced symbiotic genotypes relative to non-symbiotic ones. Our results provide a rare set of field observations against which predictions from theoretical and experimental work in the evolutionary ecology of RNS can be compared.