They appear in the fossil record in the late Archaean, about 3.5 billion years ago, and in the Proterozoic, from 2.5 billion years ago, they are believed to have been mostly made by cyanobacteria. The University of California Museum of Paleontology has a great introduction to cyanobacterial fossils and Proterozoic life on its history of life website.
Stromatolites are rare today, and one of the main hypotheses for this is that herbivore grazers would readily attack such a concentrated source of food. The best known examples of modern stromatolites are those in Shark Bay, Western Australia, where they live in highly saline water, which is not conducive to such herbivore grazers.
So it's a surprise to hear that a small stromatolite colony has been found among the rocks of the famous Giant's Causeway in Northern Ireland. The colony is in brackish water that is exposed to waves and potential grazers. It was found by environmental scientists from the University of Ulster who were out looking for other some geological features.
|The basaltic columns of the Giant's Causeway, where the stromatolite was found.|
The Causeway itself is an extraordinary geological structure, composed of interlocking "pillars" of basalt formed by volcanic activity. These pillars are more or less hexagonal in cross-section, making it look like a set of giant stepping stones.
A little more browsing on Wikipedia throws up a list of other modern stromatolites around the world, some of which are in fresh water. It's amazing how quickly the news report on the new stromatolite find was picked up and incorporated into Wikipedia.
I'm quite a fan of stromatolites. I had the opportunity to see some fossilized stromatolites in the field when my palaeontology class in college went out to upstate New York, to the fossil-rich area around Utica. Unfortunately most fossils look much better in the full glare of the sun (and the excitement of the moment!) than when they are photographed:
|Stromatolite fossils in the ground. There's really something there, I swear!|