(I’m even further behind on things than usual, so this is not that “hot” off the press, but the walking lungfish can’t not be posted on.)
The evolution of new traits serving new functions is always a bit of a chicken and egg problem. Why would you need wings if you don’t fly, and how could you start flying without them? Why would you need legs if you don’t walk, and how would you walk without legs?
Often, as in the case of wings, the most likely answer is that the trait originally had a different function that didn’t necessitate a “perfect” version of it. Wings that are no good for flying could be anything from egg-warmers/shades through mate attraction devices to balancing organs for prey-wrestling predatory dinosaurs (latter idea from Fowler et al., 2011, which by now has probably gone as viral as scientific papers can).
With legs, though, it seems that the chicken really did come first. We’ve known for a long time that coelacanths (which are somewhat distantly related to vertebrates with legs) sometimes move their pectoral and pelvic fins in an alternating rhythm that resembles walking. (IIRC you can find a fair few YouTube videos in which they are filmed doing that.) Nonetheless, coelacanths use this movement for swimming. They don’t actually get down and plod along the bottom.
Lungfish, however, do. King et al. (2011) videoed them doing it.
Just to be clear, the animal in question is the West African lungfish (Protopterus annectens). Unlike the respectable paddles of the Australian species, its spindly paired appendages barely even deserve to be called fins, let alone legs. (Drawing below from King et al., 2011)
Yet this creature uses its pelvic fins to propel itself along the bottom in a variety of ways. It can walk with alternating “steps”, it can bound by moving both fins at once, and sometimes it just ambles along in a slightly irregular way (videos here). If there’s no traction on the bottom of the tank, it slips and can’t get anywhere, which indicates that it does indeed propel itself by pushing against the bottom with its hind fins. And sometimes, when the fins push off, you can see part of the body come clear off the ground.
(Interestingly, the lungfish walks and bounds only with its hind fins. Meanwhile, the pectorals flail around doing other things, but they don’t engage with the floor. The diagram above gives a clue why: the animal has huge, air-filled lungs – the grey blob – that help its front half float. It doesn’t need its forefins to stroll around.)
Given how un-leglike the fins of African lungfish are, it is obvious that walking underwater doesn’t require anything as sophisticated as ankles or toes or, heck, even proper fins. Just about any ancient lobe-finned fish we know could have been capable of it. Could this be how our ancestors took their first unknowing steps towards land? Were they bottom-dwelling fish that patrolled their territories in a stately fin-walk? Did increasingly leg-like fins just help them do that better rather than breaking new ground? As the authors remind us, we already know that many of the earliest tetrapods – creatures with true legs – lived in water. If less tetrapod-like creatures could walk, then the picture fits quite nicely together.
And speaking of chickens and eggs, once again nature proves how much human incredulity is worth. Just because you don’t know what to do with half a wing, just because you don’t think X is possible without Y, doesn’t mean solutions don’t exist. Studying nature is a life-long lesson in humility in that way.
Fowler DW et al. (2011) The predatory ecology of Deinonychus and the origin of flapping in birds. PLoS ONE 6:e28964
King HM et al. (2011) Behavioral evidence for the evolution of walking and bounding before terrestriality in sacropterygian fishes. PNAS 108:21146-21151