Stromatolites are domes, columns, or nearly flat crusts of laminated sedimentary rocks, usually consisting of Ca-Mg carbonates. Stromatolites result from lithification of microbial mats, which are benthic microbial ecosystems where microorganisms arrange themselves in layers according to their physiology. Despite a century of research, the hypothesis of stromatolite genesis by lithification of microbial mats remains controversial, and a convincing explanation for how stromatolites arise from microbial mats is still lacking. In this work, we analyze in detail a stromatolite from Lagoa Vermelha, a coastal hypersaline lagoon in Rio de Janeiro State, Brazil. The stromatolite presents a laminated core and thrombolitic regions at the periphery. Both thrombolitic and laminated facies consist of fine-grained authigenic minerals with minor contributions of bioclasts and quartz grains. X-ray diffraction shows aragonite, high-magnesium calcite (HMC) containing about 17% MgCO3, a very-high-Mg calcite (VHMC) containing 29–46% MgCO3, and small amounts of quartz and pyrite. Scanning electron microscopy of polished samples coupled to energy-dispersive X-ray analysis (EDS) showed that each lamina was composed of 1–4 distinct mineral phases embedded within each other, indicating sequential steps of precipitation of Ca-Mg carbonates under distinct biogeochemical conditions. The coexistence of different phases in a single lamina suggests that several processes contribute to mineral deposition as the incipient stromatolite laminae are left behind by microorganisms from the lower layers of the microbial mat when they grow and/or move upwards.