409 million years ago, Early Devonian (Pragian), Yunnan, China
Described in October 2012, Tungsenia paradoxa is the oldest and most primitive known tetrapodomorph, the vertebrate group that includes the tetrapods (limbed-vertebrates) and their immediate fish relatives (Eusthenopteron, Gogonasus, Tiktaalik etc). It was a small (less than 20 cm long) predator that lived in shallow marine waters off Early Devonian China.
This critter possessed key tetrapodomorph characters (teardrop shaped recess in front of the optic foramen, hole for the pituitary vein in the basipterygoid process, flat parasymphysial dental plates etc) combined with a host of archaic features that it shared with with the earliest representatives of the dipnomorph clan (lungfishes and their kin, the sister-group to the tetrapodomorphs) including a broad parasphenoid and paired internasal pits.
This represents a very early stem-tetrapod fish, only a few million years after the tetrapodomorphs and dipnomorphs went their separate evolutionary ways during the Late Silurian. The whole tetrapod dynasty, from finches to frogs, cats to chasmosaurs, not to mention Homo sapiens, can trace their lineage to a little fishy like this.
SOURCE: Jing Lu, Min Zhu, John A. Long, Wenjin Zhao, Tim J. Senden, Liantao Jia & Tuo Qiao (2012) The earliest known stem-tetrapod from the Lower Devonian of China. Nature Communications 3, Article number:1160
For the most part - unfortunately some reporters are assuming that since this is a "stem-tetrapod", it must also mean that it had limbs and crawled out of the water...