The Scientific American Editor's blog has a very nice summary of some recent ideas about the transition from living in the sea to living in land . The bones of the inner ear of terrestrials, for example, may have been derived from a breathing hole that initially allowed clean water to be pumped over the gills independently of the mouth. (Nearer to my own work, the swim bladders of fishes were adapted to generate terrestrial lungs, and they have a whole slew of molecular similarities to our airbags.)
UPDATE: the lung/swimbladder story is not as simple as I thought. Apparently both structures emerged multiple times during fish evolution, and the current similarity is an example of convergent evolution. Hat tip to Lloyd .
In summary, a whole lot of body structures had to get refitted for this transition to happen. The post has very nice explanations, and lots of links!