Der Stromatolith oder auch „geschichteter Stein“, wurde zum ersten Mal von einem Steinbruch am Heeseberg (Jerxheim, Harzvorland) im Jahre 1908 durch den Mineralogen Ernst Kalkowski (1851-1937) beschrieben. Kalkowski vergleicht dieses Fossil zunächst mit Schwämmen, stellt aber dann richtig fest, das es sich eigentlich um ein durch Mikroorganismen gebildetes Sedimentgestein handelt. Cyanobakterien und andere autotrophe Mikroben formen lange Ketten von Zellen, diese Filamente überwuchern das Substrat mit einer schleimigen Schicht und werden ihrerseits von neuen Sedimenten zugedeckt. Um zu überleben, da sie ja auf Sonnenlicht angewiesen sind, wachsen die Mikroorganismen durch diese Sedimentschicht, wo sie sich wieder flächig ausbreiten. Wird dies nun oft und lange genug wiederholt, entwickelt sich ein fein laminiertes Gestein – ein Stromatolith.

Die ältesten Gesteine der Erde sind um die 4 Milliarden Jahre datiert. Die ältesten indirekten Hinweise auf Leben sind um die 3,4 bis 3,7 Milliarden Jahre alt und stammen aus dem Grafit von Isua in Westgrönland. Die besondere chemische Verteilung von Kohlenstoff, von denen es mehrere Isotope gibt, in diesem Gestein lässt sich am besten durch biologische Aktivität erklären.  Die ältesten gesicherten Stromatolithen sind auch um die 3,5 Milliarden Jahre alt und aus dem australischen Apex Chert bzw. Schichten des afrikanischen Barbertown Mountain Land beschrieben. Eine Sensation stellte daher in 2016 die angebliche Entdeckung von 3,7 Milliarden Jahre Stromatolithen dar, die in den selben Gesteinen von Westgrönland entdeckt wurden, die auch die chemischen Lebenssignaturen enthalten. Die Form und die Verteilung der chemischen Elemente in den Gebilden sprechen laut den Autoren der Studie dafür, das es sich um echte Stromatolithen handelt. Allerdings gibt es rezente Beispiele von Sedimentstrukturen, die sich durch Entgasungen in schlammigen Sedimenten bilden, die ähnliche Formen, aber ohne Zutun von Lebensformen, aufweisen können.

Noch überraschender ist aber eine erst kürzlich publizierte Entdeckung. In 3,7 bis 4,3 Milliarden Jahre alten Gesteinen aus dem hohen Norden von Kanada wurden kleine, röhrenförmige Strukturen beschrieben. Laut den Autoren der Studie könnte es sich dabei um Fossilien von fadenförmigen Bakterienkolonien handeln, da ähnliche Strukturen von Kolonien von Mikroorganismen, die heute heiße Tiefseequellen besiedeln, bekannt sind. Sollten diese Entdeckung bestätigt werden, würde es bedeuten, das komplexe Lebensgemeinschaften bereits auf einer sehr jungen Erde (die um die 4,5 Milliarden Jahre alt ist) existierten. Das Leben auf der Erde müsste daher noch früher entstanden sein als bisher vermutet, bereits kurz nach der Entstehung des Planeten.

Stromatolithen spielen aber nicht nur bei der Frage nach dem Ursprung des Lebens eine Rolle, sondern haben heutzutage auch eine wirtschaftliche Bedeutung. Zwischen 2,5 und einer halben Milliarden Jahre waren Stromatolithen an den Stränden der ersten Kontinente weit verbreitet. Banded Iron Formations (oder BIFs) sind laminierte, 3,8-1,8 Milliarden Jahre alte quarzreiche Gesteine, in denen sich Schichten aus Quarzit mit eisenreichen Lagen abwechseln. In der sauerstofffreien Umgebung der primitiven Erde löste sich Eisen, das aus vulkanischer Aktivität und Verwitterung stammt, völlig in den Ozeanen auf. Erst als die ersten Mikroorganismen freien Sauerstoff bildeten, reagierte das gelöste Eisen damit und formte die eisenhaltigen Lagen, die heute abgebaut werden.

Im Ordovizium (um die 400 Millionen Jahre) und bis in die Kreide (um die 65 Millionen Jahre) hinein, werden die Stromatolithen-bildende Mikroorganismen langsam aber sicher von höheren Organismen verdrängt. Sie ziehen sich daher in extreme Lebensräume zurück, wo die Konkurrenz bedeutend niedriger ist und sie bis heute erfolgreich überleben. Bekannt sind die modernen Vorkommen entlang der Meeresküste der australischen Shark-Bay. Hier bilden sie im Salzwasser bis zu einem Meter hohe Steinsäulen, aber auch ring- bis pilzförmige Strukturen oder einfache Knollen.