Soil bacteria that also form mutualistic symbioses in plants encounter two major levels of selection. One occurs during adaptation to and survival in soil, and the other occurs in concert with host plant speciation and adaptation. Actinobacteria from the genus Frankia are facultative symbionts that form N(2)-fixing root nodules on diverse and globally distributed angiosperms in the "actinorhizal" symbioses. Three closely related clades of Frankia sp. strains are recognized; members of each clade infect a subset of plants from among eight angiosperm families. We sequenced the genomes from three strains; their sizes varied from 5.43 Mbp for a narrow host range strain (Frankia sp. strain HFPCcI3) to 7.50 Mbp for a medium host range strain (Frankia alni strain ACN14a) to 9.04 Mbp for a broad host range strain (Frankia sp. strain EAN1pec.) This size divergence is the largest yet reported for such closely related soil bacteria (97.8%-98.9% identity of 16S rRNA genes). The extent of gene deletion, duplication, and acquisition is in concert with the biogeographic history of the symbioses and host plant speciation. Host plant isolation favored genome contraction, whereas host plant diversification favored genome expansion. The results support the idea that major genome expansions as well as reductions can occur in facultative symbiotic soil bacteria as they respond to new environments in the context of their symbioses.