The ribosomal RNA molecule is an ideal model for evaluating the stability of a gene product under desiccation stress. We isolated 8 Nostoc strains that had the capacity to withstand desiccation in habitats and sequenced their 16S rRNA genes. The stabilities of 16S rRNAs secondary structures, indicated by free energy change of folding, were compared among Nostoc and other related species. The results suggested that 16S rRNA secondary structures of the desiccation-tolerant Nostoc strains were more stable than that of planktonic Nostocaceae species. The stabilizing mutations were divided into two categories: (1) those causing GC to replace other types of base pairs in stems and (2) those causing extension of stems. By mapping stabilizing mutations onto the Nostoc phylogenetic tree based on 16S rRNA gene, it was shown that most of stabilizing mutations had evolved during adaptive radiation among Nostoc spp. The evolution of 16S rRNA along the Nostoc lineage is suggested to be selectively advantageous under desiccation stress.