Najstarejši znani fosil je stromatolit (v grščini pomeni “skala vzmetnice”) izpred 2.74 milijarde let. Stromatolit je večplastna akrecijska struktura, ki nastane, ko bakterije, zlasti fotosintetične cianobakterije, ujamejo plasti usedline med biofilmi, ki jih ustvarijo.
Stromaliti so različnih oblik in velikosti, vključno s stožci, stebri in razvejanimi vrstami. Dolgo časa je veljalo, da stromatoliti v sedanjosti ne obstajajo (preveč pašnih organizmov), dokler jih niso odkrili v izoliranih, zelo slanih ekosistemih, kot sta zaliv morskih psov in jezero Thetis v Avstraliji ter Cuatro Cienegas v Mehiki. Tako kot podkovnjaki tudi stromatoliti zaradi svoje starosti veljajo za “žive fosile”.
Najstarejši znani fosil stromatolitov je skoraj petkrat starejši od najstarejšega fosila večceličnega organizma, ki sega pred približno 600 milijoni let. Obstaja še nekaj starejših stromalitu podobnih tvorb, ki segajo še dlje kot 2.74 milijarde let, tudi kandidati za najstarejši fosil, vendar nobena ni potrjena s strani znanstvene skupnosti.
Stromatoliti so znaki organizmov, ki so morda imeli pomembno vlogo pri spreminjanju Zemlje kot kateri koli drug organizem: cianobakterije. Te fotosintetske bakterije so v velikem obsegu pretvorile ogljikov dioksid v kisik, kar je spremenilo sestavo atmosfere in povzročilo tako imenovano »kisikovo katastrofo«, ki bi ubila številne druge takrat žive organizme, za katere je bil kisik strupen.
Obstajajo nebiološke strukture, podobne stromatolitu, ki jih je mogoče zamenjati za najstarejši znani fosil, vendar ne pomenijo nič drugega kot obarjanje drobnih kristalov. Te danes niso opazili, vendar se domneva, da so bile razmere v oceanih preteklosti morda zrele za njihovo ustvarjanje.
Najstarejši znani fosili živali se pojavijo šele v srednjem Ediakarskem obdobju, pred približno 600 milijoni let. Sem spadajo različne preproste spužve, cnidarije (kot so sodobne hidre) in celo preproste dvostranske spužve (organizmi z dvostransko simetrijo), ki spominjajo na drobne balone. Te živali so se pojavile kmalu po največji ledeni dobi v zgodovini planeta, ki je povzročila nastanek ledenikov na morski gladini na ekvatorju.