In contrast to obligate bacteria, facultative symbiotic bacteria are mainly characterized by genome enlargement. However, the underlying relationship of this feature with adaptations to various habitats remains unclear. In this study, we used the global genome data of Nostoc strains, including 10 novel genomes sequenced in this study and 26 genomes available from public databases, and analyzed their evolutionary history. The evolutionary boundary of the real clade of Nostoc species was identified and was found to be consistent with the results of polyphasic taxonomy. The initial ancestral species of Nostoc was demonstrated to be consistent with a facultative symbiotic population. Further analyses revealed that Nostoc strains tended to shift from facultative symbiosis to a free-living one, along with an increase in genome sizes during the dispersal of each exterior branch. Intracellular symbiosis was proved to be essentially related to Nostoc evolution, and the adaptation of its members to free-living environments was coupled with a large preference for gene acquisition involved in gene repair and recombination. These findings provided unique evidence of genomic mechanisms by which homologous microbes adapt to distinct life manners and external environments.