Cyanobacteria are among the most diverse prokaryotic phyla, with morphotypes ranging from unicellular to multicellular filamentous forms, including those able to terminally (i.e., irreversibly) differentiate in form and function. It has been suggested that cyanobacteria raised oxygen levels in the atmosphere around 2.45-2.32 billion y ago during the Great Oxidation Event (GOE), hence dramatically changing life on the planet. However, little is known about the temporal evolution of cyanobacterial lineages, and possible interplay between the origin of multicellularity, diversification of cyanobacteria, and the rise of atmospheric oxygen. We estimated divergence times of extant cyanobacterial lineages under Bayesian relaxed clocks for a dataset of 16S rRNA sequences representing the entire known diversity of this phylum. We tested whether the evolution of multicellularity overlaps with the GOE, and whether multicellularity is associated with significant shifts in diversification rates in cyanobacteria. Our results indicate an origin of cyanobacteria before the rise of atmospheric oxygen. The evolution of multicellular forms coincides with the onset of the GOE and an increase in diversification rates. These results suggest that multicellularity could have played a key role in triggering cyanobacterial evolution around the GOE.