Stromatolites are the oldest known fossilized formations built by cyanobacteria (blue-green algae). The word stromatolite is Greek for "stony carpet", because of its natural look. Stromatolites were formed by the layering of reef structures just above or near the surface of the water that developed, as sediments become entrapped (fossilized) within colonies of cyanobacteria.

These cyanobacteria, were responsible, during earth's early evolution about 3 billion years ago, for the formation of much of the planet's breathable oxygen by photosynthesis, which allowed for the development of oxygen-breathing organisms.

Stromatolites lived in huge masses that were built layer upon layer of algal mats or extensive reefs. They thrived in warm aquatic environments, in much the same way coral does. Masses of cyanobacteria on the sea floor deposited calcium carbonate in layers or domes. Stromatolites will appear as variously sized arches, spheres, or domes because they trap sand and assorted particulate material in their sticky, filamentous strands. They can vary in size, with large ones being more than a yard high and close to four feet in diameter.

Stromatolites were the dominant life forms of cyanobacteria, here on earth for over 2 billion years. The stromatolites began to decline about 700 million years. One theory suggests that herbivorous eukaryotes (cells with a nucleus) may be responsible for their decline. They evolved at about this time and began to feed extensively on the growing stromatolites. Today, stromatolites are nearly extinct, living a precarious existence in only a few localities worldwide. They are mostly found in restricted habitats, where predators that feed on algae or burrowing animals that destroy the algal mats are absent or rare, with low levels of grazing, such as the shallow saline waters of Shark Bay, Australia.