Cyanobacteria were the ultimate ancestor of all plastids and, for much of Earth's history, the only source of biogenic oxygen and a major source of fixed carbon and nitrogen. One cyanobacterial clade, subsections IV+V, is characterized by multicellularity and cell differentiation, with many members bearing specialized nitrogen-fixing (or diazotrophic) heterocysts and encysting akinetes [1-3]. Molecular clock estimates of the divergence time of this clade are highly variable, ranging from similar to 2,000 Ma (mega-annum) [4-9] to similar to 500 Ma [10]. The older estimates are invariably calibrated by putative akinete fossils from Paleoproterozoic-Mesoproterozoic rocks around 2,100-1,400 Ma [3, 11, 12]. However, the interpretation of these fossils as akinetes has been questioned [13], and the next oldest akinete and heterocyst fossils are similar to 410 Ma [14]. Thus, the scarcity of reliable heterocystous cyanobacterial fossils significantly hampers our understanding of the evolution of complex multicellularity among cyanobacteria, their role in regulating geochemical cycles in the geological past, and our ability to calibrate cyanobacterial molecular clocks. Here, we report Tonian (similar to 1,000-720 Ma) filamentous cyanobacteria that are characterized by large cells, binary fission (for filament elongation), hormogonia (for asexual reproduction and dispersal), probable akinetes (for survival in adverse conditions), and by implication, diazotrophic heterocysts. The new fossils provide a minimum age calibration on the divergence of subsections IV+V and place a firm constraint on the evolution of akinetes and heterocysts.