The recognition and understanding of the early fossil record on Earth is vital to the success of missions searching for life on other planets. Despite this, the evidence for life on Earth before ~3.0 Ga remains controversial. The discovery of new windows of preservation in the rock record more than 3.0 Ga would therefore be helpful to enhance our understanding of the context for the earliest life on Earth. Here we report one such discovery, a ~3.4 Ga sandstone at the base of the Strelley Pool Formation from the Pilbara of Western Australia, in which micrometre-sized tubular structures preserve putative evidence of biogenicity. Detailed geological mapping and petrography reveals the depositional and early diagenetic history of the host sandstone. We demonstrate that the depositional environment was conducive to life and that sandstone clasts containing putative biological structures can be protected from later metamorphic events, preserving earlier biological signals. We conclude from this that sandstones have an exciting taphonomic potential both on early Earth and beyond.