Organo-sedimentary deposits that result from fine-grained sediment trapping, binding, and likely precipitation (of carbonate) by microbes in flat-mat, branching, and dome-shaped constructions are termed microbialites. They were first identified as stromatolites by paleontologists well before the discovery of cyanobacteria that build the same kinds of structures in contemporary settings around the world. Earth’s earliest life forms were prokaryotes (bacteria and bacteria-like forms) that reproduced under anaerobic conditions and later produced increasingly aerobic conditions. Stromatolites persisted through later Archean and Proterozoic times through the subsequent Phanerozoic to the present. At the start of the Cambrian Period 538 million years ago, stromatolites continued alongside rapidly diversifying plant and animal phyla during the Cambrian explosion of eukaryotic life, which have complex cells with internal structures and tissue-grade organization in multicellular taxa. The type locality exhibiting clear examples of stromatolite structures is conserved at Lester Park near Saratoga Springs in northeastern New York State. Paleontologist James Hall (1811–1898) was the first in 1884 to assign a Latin binomen (Cryptozoon proliferum) to stromatolite fossils from Lester Park. Thereafter, reports on formally named stromatolites proliferated, as did examples from virtually all subsequent geological time intervals including the Pleistocene Epoch. However, recognition that living cyanobacteria formed stromatolites identified as Cryptozoon took place much later in 1961 with the announcement by geologist Brian W. Logan (1933–2008) who described modern constructions in Hamlin Pool, Shark Bay, Western Australia. Initially, Shark Bay was regarded as a one-of-a-kind sanctuary for stromatolites living under restricted conditions with elevated levels of salinity that prohibited competition or grazing by eukaryotes. Most notably, among other settings with living stromatolites discovered and described since then are the Bahamas, East African rift lakes, Mexico’s Baja California, and saline lakes in Argentina. This report reviews the history of discoveries of modern-day stromatolites, more commonly called microbialites by biologists. All are predicated on the ground-breaking efforts of geologists and paleontologists who first described fossil stromatolites but were unaware of their living counterparts. The Lester Park locality is highlighted together with a master list of other North American localities that feature purported Cryptozoons.