Cyanobacteria, the oldest oxygenic phototrophs on the planet, once made the most significant impact on sediments and left an impressive fossil record of organo-sedimentary structures. Today, cyanobacteria dominate extreme environments where they participate in sediment production, construction and destruction, and leave characteristic, often species-specific, traces of their activities. Microbial ecosystems at the sediment-water interface are built and supported by cyanobacteria as the principal primary producers. Cyanobacterial photosynthesis promotes carbonate precipitation, delivering new sediment particles. Cyanobacterial growth, movement and behavioral responses often guide the depositional process and shape the resulting sedimentary structures. Conversely, cyanobacterial colonization and growth is also guided by changes in depositional environment. Cyanobacterial primary production at the sediment-water interface, coupled with rapid bacterial oxidation of this organic product, maintains steep redox gradients, creating additional metabolic niches. The consequent changes in mineral solubility promote biogeochemical cycling of elements and may lead to recrystallization and rearrangement of minerals. Destruction and alteration of sediments may be caused by cyanobacterial activities indirectly, or be carried out directly by euendolithic cyanobacteria which actively penetrate carbonate substrates. Evidence of both sediment-constructing and -destructing cyanobacterial behavior is found in carbonate deposits of the Mesoproterozoic age. As pioneer settlers on marine, freshwater and terrestrial sedimentary deposits, modern cyanobacteria prepare the ground for successive invasion and expansion of eukaryotic flora and fauna. In the historical context, and on a geological time scale, analogous sequences of events illustrate the evolutionary progression of life’s complexity, as cyanobacterially supported microbial ecosystems of marine and terrestrial environments gave way to eukaryote-dominated ones.