Within prokaryotes cyanobacteria represent one of the oldest and morphologically most diverse phyla on Earth. The rise of oxygen levels in the atmosphere 2.32-2.45 billion years ago is assigned to the photosynthetic activity of ancestors from this phylum. Subsequently cyanobacteria were able to adapt to various habitats evolving a comprehensive set of different morphotypes. In a recent study we showed that this evolution is not a gradual transition from simple unicellular to more complex multicellular forms as often assumed. Instead complexity was lost several times and regained at least once. An understanding of the genetic basis of these transitions would be further strengthened by phylogenomic approaches. However, considering that new methods for phylogenomic analyses are emerging, it is unfortunate that genomes available today are comprised of an unbalanced sampling of taxa. We propose avenues to remedy this by identifying taxa that would improve the representation of phylogenetic diversity in this phylum.