Stromatolites are abundant in shallow marine sediments deposited before the evolution of animals, but in the modern ocean they are restricted to locations where the activity of animals is limited. Overall decline in the abundance of stromatolites has, therefore, been attributed to the evolution of substrate-modifying metazoans, with Phanerozoic stromatolite resurgences attributed to the aftermaths of mass extinctions. Here we use a comprehensive stratigraphic database, the published literature, and a machine reading system to show that the rock record–normalized occurrence of stromatolites in marine environments in North America exhibits three phases: an initial Paleoproterozoic (ca. 2500 Ma) increase, a sustained interval of dominance during the Proterozoic (2500–800 Ma), and a late Neoproterozoic (700–541 Ma) decline to lower mean prevalence during the Phanerozoic (541–0 Ma). Stromatolites continued to exhibit large changes in prevalence after the evolution of metazoans, and they transiently achieved Proterozoic-like prevalence during the Paleozoic. The aftermaths of major mass extinctions are not well correlated with stromatolite resurgence. Instead, stromatolite occurrence is well predicted by the prevalence of dolomite, a shift in carbonate mineralogy that is sensitive to changes in water-column and pore-water chemistry occurring during continent-scale marine transgressive-regressive cycles.