Cyanobacteria (Blue-green Algae).

Cyanobacteria are the earliest creatures to be preserved in the fossil record. Stromatolites, calcareous structures formed during the growth of dense colonies of cyanobacteria, have been found in rocks 2.5 billion years old, and the fossil record shows that through the Proterozoic aeon, from about 2500 million to 600 million years ago, the cyanobacteria were the dominant life-form on Earth.
Stromatolites formed by living cyanobacteria can be seen in various parts of the world today, most notably in Shark Bay, Western Australia.

Here is a link to an interesting article in New Scientist (6 March, 2002) concerning a controversy over a claim that fossilized cyanobacteria have been identified in rocks 3.5 billion years old.

Until quite recently (the last 20 years or so), the blue-green algae were called the Cyanophyta (or Myxophyta) and classified amongst the plants. Their current inclusion in the phylum Bacteria is the result of genetic and electron microscopical studies, and is part of an important shift in the way we view the relationships between living creatures.

Structurally, the cyanobacteria have a great deal in common with the plastids (chlorophyll-containing bodies) within the cells of algae and all higher plants. This and other considerations has led to our present belief that the modern algae and higher plants are the descendants of an endosymbiotic relationship established by blue-green algae within primitive nucleated cells during the earliest stages of life on Earth.

The cyanobacteria are distinguished from the other photosynthetic bacteria by their ability to produce oxygen. They also possess a mucilaginous sheath of cellulose fibrils varying in thickness from one genus to another, which enables the filamentous forms to glide slowly in a longitudinal direction -- a motion which has not been fully explained.

The two classes of cyanobacteria are the Coccogoneae (coccoid or spherical) and the Hormogoneae (filamentous).