Many filamentous cyanobacteria reduce atmospheric nitrogen in specialized differentiated cells called heterocysts. Here we present evidence that shows that members of the unicellular non-heterocyst-differentiating genus Chroococcidiopsis and the filamentous heterocyst-differentiating cyanobacteria are each other's closest living relatives. Distance, maximum-parsimony, and maximum-likelihood analyses of complete small subunit ribosomal RNA gene sequences yielded highly congruent support for the monophyly of Chroococcidiopsis and the heterocyst-differentiating cyanobacteria. Our results demonstrate that the order Pleurocapsales, which traditionally contains Chroococcidiopsis, is a polyphyletic assemblage with the ability to reproduce by multiple fission having arisen independently at least twice during the cyanobacterial radiation. Our data also reject Myxosarcina as a sister taxon to Chroococcidiopsis, indicating that the numerous presumed shared derived characters thought to unite the two genera evolved independently. The sequence divergence within the Chroococcidiopsis lineage is comparable to and probably exceeds that in the entire heterocyst-differentiating lineage. Chroococcidiopsis forms unique survival cells under nitrogen-limiting conditions, and the sister group relationship with the heterocystous cyanobacteria shown here suggests that differentiation of these cells and heterocysts may be related processes.