Stromatolites are the least controversial evidence of early life; they are organosedimentary structures resulting from the growth and metabolic activity of microorganisms1. Before this report, however, the oldest well established occurrence was in the 2,900-3,000 Myr Pongola Supergroup of South Africa2; five or six additional occurrences are known from the later Archean3. The only proposed example from older rocks is of a possibly stromatolitic microfabric from 3,500 Myr cherts in South Africa4; as yet that interpretation has not been supported by the discovery of macroscopic stromatolites. Here we describe stromatolites 3,400-3,500-Myr old from the Pilbara Block of Western Australia. These are the oldest firmly established biogenic deposits now known from the geological record.