The most ancient fossils represent very simple, single celled, life-forms preserved in very fine grained sediments. They are often very difficult to recognise and the scientific literature is scattered with arguments over whether a particular set of microscopic objects do or do not represent former living cells. One of the most convincing evidences come from the study of stromatolites. Stromatolites are structures which form from colonies of bacteria. These colonial structures form 'mats' (http://nai.arc.nasa.gov/index.cfm?page=focus1, http://nai.arc.nasa.gov/_global/shockwave/g3_matgallery.swf) or mounds, which trap fine-grained limestone sediment. The bacteria themselves decay away but the fine-grained limestone mud preserves the detailed structure of the algal mat as evidence of former living organisms. They form today in warm salty shallow marine conditions. Examples of stromatolites from the geological record are found at
The oldest authenticated stromatolites are from the rocks of the North Pole region of the Pilbara area, western Australia. They are contained in a sequence of unmetamorphosed sediments and lavas 3500 million years old. The sediments are thought to represent shallow water sands and evaporites (see http://www.carleton.ca/~tpatters/teaching/intro/precambrian/precambrian7.html). Stromatolites are also reported from the ca. 3400 million year Barberton area in south Africa and from 2900 million-year rocks in the Belingwe area of Zimbabwe.