Cyanobacteria belonging to the genusNostoccomprise free-living strains and also facultative plant symbionts. Symbiotic strains can enter into symbiosis with taxonomically diverse range of host plants. Little is known about genomic changes associated with evolutionary transition ofNostocfrom free-living to plant symbiont. Here, we compared the genomes derived from 11 symbioticNostocstrains isolated from different host plants and infer phylogenetic relationships between strains. Phylogenetic reconstructions of 89 Nostocales showed that symbioticNostocstrains with a broad host range, entering epiphytic and intracellular or extracellular endophytic interactions, form a monophyletic clade indicating a common evolutionary history. A polyphyletic origin was found forNostocstrains which enter only extracellular symbioses, and inference of transfer events implied that this trait was likely acquired several times in the evolution of the Nostocales. SymbioticNostocstrains showed enriched functions in transport and metabolism of organic sulfur, chemotaxis and motility, as well as the uptake of phosphate, branched-chain amino acids, and ammonium. The genomes of the intracellular clade differ from that of otherNostocstrains, with a gain/enrichment of genes encoding proteins to generate l-methionine from sulfite and pathways for the degradation of the plant metabolites vanillin and vanillate, and of the macromolecule xylan present in plant cell walls. These compounds could function as C-sources for members of the intracellular clade. Molecular clock analysis indicated that the intracellular clade emerged ca. 600 Ma, suggesting that intracellularNostocsymbioses predate the origin of land plants and the emergence of their extant hosts.