Cyanobacteria are among the most ancient of evolutionary lineages, oxygenic photosynthesizers that may have originated before 3.0 Ga, as evidenced by free oxygen levels. Throughout the Precambrian, cyanobacteria were one of the most important drivers of biological innovations, strongly impacting early Earth's environments. At the end of the Archean Eon, they were responsible for the rapid oxygenation of Earth's atmosphere during an episode referred to as the Great Oxidation Event (GOE). However, little is known about the origin and diversity of early cyanobacterial taxa, due to: (1) the scarceness of Precambrian fossil deposits; (2) limited characteristics for the identification of taxa; and (3) the poor preservation of ancient microfossils. Previous studies based on 16S rRNA have suggested that the origin of multicellularity within cyanobacteria might have been associated with the GOE. However, single‐gene analyses have limitations, particularly for deep branches. We reconstructed the evolutionary history of cyanobacteria using genome scale data and re‐evaluated the Precambrian fossil record to get more precise calibrations for a relaxed clock analysis. For the phylogenomic reconstructions, we identified 756 conserved gene sequences in 65 cyanobacterial taxa, of which eight genomes have been sequenced in this study. Character state reconstructions based on maximum likelihood and Bayesian phylogenetic inference confirm previous findings, of an ancient multicellular cyanobacterial lineage ancestral to the majority of modern cyanobacteria. Relaxed clock analyses provide firm support for an origin of cyanobacteria in the Archean and a transition to multicellularity before the GOE. It is likely that multicellularity had a greater impact on cyanobacterial fitness and thus abundance, than previously assumed. Multicellularity, as a major evolutionary innovation, forming a novel unit for selection to act upon, may have served to overcome evolutionary constraints and enabled diversification of the variety of morphotypes seen in cyanobacteria today.