BACKGROUND: An ancient cyanobacterial incorporation into a eukaryotic organism led to the evolution of plastids (chloroplasts) and subsequently to the origin of the plant kingdom. The underlying mechanism and the identities of the partners in this monophyletic event remain elusive. METHODOLOGY/PRINCIPAL FINDINGS: To shed light on this evolutionary process, we sequenced the genome of a cyanobacterium residing extracellularly in an endosymbiosis with a plant, the water-fern Azolla filiculoides Lam. This symbiosis was selected as it has characters which make it unique among extant cyanobacterial plant symbioses: the cyanobacterium lacks autonomous growth and is vertically transmitted between plant generations. Our results reveal features of evolutionary significance. The genome is in an eroding state, evidenced by a large proportion of pseudogenes (31.2%) and a high frequency of transposable elements (approximately 600) scattered throughout the genome. Pseudogenization is found in genes such as the replication initiator dnaA and DNA repair genes, considered essential to free-living cyanobacteria. For some functional categories of genes pseudogenes are more prevalent than functional genes. Loss of function is apparent even within the ‘core’ gene categories of bacteria, such as genes involved in glycolysis and nutrient uptake. In contrast, serving as a critical source of nitrogen for the host, genes related to metabolic processes such as cell differentiation and nitrogen-fixation are well preserved. CONCLUSIONS/SIGNIFICANCE: This is the first finding of genome degradation in a plant symbiont and phenotypically complex cyanobacterium and one of only a few extracellular endosymbionts described showing signs of reductive genome evolution. Our findings suggest an ongoing selective streamlining of this cyanobacterial genome which has resulted in an organism devoted to nitrogen fixation and devoid of autonomous growth. The cyanobacterial symbiont of Azolla can thus be considered at the initial phase of a transition from free-living organism to a nitrogen-fixing plant entity, a transition process which may mimic what drove the evolution of chloroplasts from a cyanobacterial ancestor.