Calcification and silicification processes of cyanobacterial mats that form stromatolites in two caldera lakes of Niuafo‘ou Island (Vai Lahi and Vai Si‘i) were evaluated, and their importance as analogues for interpreting the early fossil record are discussed. It has been shown that the potential for morphological preservation of Niuafo‘ou cyanobacteria is highly dependent on the timing and type of mineral phase involved in the fossilization process. Four main modes of mineralization of cyanobacteria organic parts have been recognized: (i) primary early postmortem calcification by aragonite nanograins that transform quickly into larger needle-like crystals and almost totally destroy the cellular structures, (ii) primary early postmortem silicification of almost intact cyanobacterial cells that leave a record of spectacularly well-preserved cellular structures, (iii) replacement by silica of primary aragonite that has already recrystallized and obliterated the cellular structures, (iv) occasional replacement of primary aragonite precipitated in the mucopolysaccharide sheaths and extracellular polymeric substances by Al-Mg-Fe silicates. These observations suggest that the extremely scarce earliest fossil record may, in part, be the result of (a) secondary replacement by silica of primary carbonate minerals (aragonite, calcite, siderite), which, due to recrystallization, had already annihilated the cellular morphology of the mineralized microbiota or (b) relatively late primary silicification of already highly degraded and no longer morphologically identifiable microbial remains. Key Words: Stromatolites—Cyanobacteria—Calcification—Silicification—Niuafo‘ou (Tonga)—Archean. Astrobiology 12, 535–548.