Some stunning fossil trackways have been discovered in Poland. The remarkable thing about them is that they're very old, about 395 million years old, and they are clearly the tracks of tetrapods. Just to put that in perspective, _Tiktaalik_, probably the most famous specimen illustrating an early stage of the transition to land, is younger at 375 million years, but is more primitive in having less developed, more fin-like limbs. So what we've got is a set of footprints that tell us the actual age of the transition by vertebrates from water to land had to be much, much earlier than was expected, by tens of millions of years.
Here are the trackways. Note that what they show is distinct footprints from both the front and hind limbs, not drag marks, and all that that implies: these creatures had jointed limbs with knees and elbows and lifted them and swung them forward to plant in the mud. They were real walkers.
They were also big, approximately 2 meters long. What you see here is a detailed scan of one of the footprints of this beast; no fossils of the animal itself have been found, so it's being compared to the feet of _Ichthyostega_ and _Acanthostega_, two later tetrapods. There are definite similarities, with the biggest obvious difference being how much larger the newly-discovered animal is. [Per Ahlberg makes an appearance in a video to talk about the size and significance of the mystery tetrapod](http://www.nature.com/nature/videoarchive/tetrapods/index.html).
What's it all mean? Well, there's the obvious implication that if you want to find earlier examples of the tetrapod transition, you should look in rocks that are about 400 million years old or older. However, it's a little more complicated than that, because the mix of existing fossils tells us that there were viable, long-lasting niches for a diversity of fish, fishapods, and tetrapods that temporally coexisted for a long period of time; the evolution of these animals was not about a constant linear churn, replacing the old model with the new model every year. Comparing them to cars, it's like there was a prolonged window of time in which horse-drawn buggies, Stanley Steamers, Model Ts, Studebakers, Ford Mustangs, and the Honda Civic were all being manufactured simultaneously and were all competitive with each other in specific markets…and that window lasted for 50 million years. Paleontologists are simply sampling bits and pieces of the model line-up and trying to sort out the relationships and timing of their origin.
The other phenomenon here is a demonstration of the spottiness of the fossil record. The Polish animal has left us no direct fossil remains; the rocks where its footprints were found formed in an ancient tide flat or lagoon, which is not a good location for the preservation of bones. This suggests that tetrapods may have first evolved in these kinds of marine environments, and only later expanded their ranges to live in the vegetated margins of rivers, where the flow of sediments is much more conducive to burial and preservation of animal remains. That complicates the story, too; not only do we have diverse stages of the tetrapod transition happily living together in time, but there may be a bit of selective fossilization going on, that only preserves some of the more derived forms living in taphonomically favorable environments.
Niedzwiedzki G, Szrek P, Narkiewicz K, Narkiewicz M, Ahlberg PE (2010) Tetrapod trackways from the early Middle Devonian period of Poland. Nature 463(7277): 43-48.