Cyanobacteria played an important role in the evolution of Early Earth and the biosphere. They are responsible for the oxygenation of the atmosphere and oceans since the Great Oxidation Event around 2.4 Ga, debatably earlier. They are also major primary producers in past and present oceans, and the ancestors of the chloroplast. Nevertheless, the identification of cyanobacteria in the early fossil record remains ambiguous because the morphological criteria commonly used are not always reliable for microfossil interpretation. Recently, new biosignatures specific to cyanobacteria were proposed. Here, we review the classic and new cyanobacterial biosignatures. We also assess the reliability of the previously described cyanobacteria fossil record and the challenges of molecular approaches on modern cyanobacteria. Finally, we suggest possible new calibration points for molecular clocks, and strategies to improve our understanding of the timing and pattern of the evolution of cyanobacteria and oxygenic photosynthesis.