A phylogenomic approach was used to study the evolution of traits in the Cyanobacteria. A cyanobacterial backbone tree was constructed using multiple concatenated sequences from whole genome sequences. Additional taxa were added using a separate alignment that contained morphological characters, SSU (small subunit) and LSU (large subunit) rDNA, rpoC, rpoD, tufA, and gyrB genes. A compartmentalization approach was then used to construct a robust phylogeny with resolved deep branches. Additional morphological characters (e.g. unicellular or filamentous growth, presence or absence of heterocysts) were coded, mapped onto the backbone cyanobacterial tree, and the ancestral character states inferred. Our analyses show that the earliest cyanobacterial lineages were likely unicellular coccoid/ellipsoidal/short rods that lived in terrestrial/freshwater environments. Later cyanobacterial lineages independently gained the ability to colonize brackish, marine, and hypersaline environments while acquiring a large number of more complex traits: sheath, filamentous growth, nitrogen fixation, thermophily, motility, and use of sulphide as an electron donor. Many of these adaptations would have been important in the appearance of dense microbial mats early in Earth's history. Complex traits such as hormogonia, heterocysts, and akinetes had a single ancestor. Within the Nostocales, hormogonia and heterocysts arose before akinetes.