Filamentous actinobacteria from the genus Frankia and diverse woody trees and shrubs together form N2-fixing actinorhizal root nodule symbioses that are a major source of new soil nitrogen in widely diverse biomes 1. Three major clades of Frankia sp. strains are defined; each clade is associated with a defined subset of plants from among the eight actinorhizal plant families 2,3. The evolution arytrajectories followed by the ancestors of both symbionts leading to current patterns of symbiont compatibility are unknown. Here we show that the competing processes of genome expansion and contraction have operated in different groups of Frankia strains in a manner that can be related to the speciation of the plant hosts and their geographic distribution. We sequenced and compared the genomes from three Frankia sp. strains having different host plant specificities. The sizes of their genomes varied from 5.38 Mbp for a narrow host range strain (HFPCcI3) to 7.50Mbp for a medium host range strain (ACN14a) to 9.08 Mbp for a broad host range strain (EAN1pec.) This size divergence is the largest yet reported for such closely related bacteria. Since the order of divergence of the strains is known, the extent of gene deletion, duplication and acquisition could be estimated and was found to be inconcert with the biogeographic history of the symbioses. Host plant isolation favored genome contraction, whereas host plant diversification favored genome expansion. The results support the idea that major genome reductions as well as expansions can occur in facultatively symbiotic soil bacteria as they respond to new environments in the context of their symbioses.