During a lecture to our second-year evolutionary biology class I introduced the concept of exaptations: features that have evolved in one environmental context but which have been co-opted to fill a different role in a changed environment. This was in the context of swim bladders/lungs, which I'll talk about in a minute, but right now I'm regretting not having read further through Lewis Held's Quirks of human anatomy before the lecture, as he's got a different, fascinating example (Held, 2009):
Darwin made an interesting observation about our fontanelles. He noted how lucky we are that these hinges were already in place (because of how skull bones grow) before they acquired the function of allowing our skull to deform during the tight squeeze of the birth process. in other words, mammalian sutures were "co-opted" as hominin hinges:
"The sutures in the skulls of young mammals have been advanced as a beautiful adaptation for adding parturition [birth]... but as sutures occur in the skulls of young birds and reptiles, which have only to escape from a broken egg, we may infer that this structure has arisen from the laws of growth, and has been taken advantage of in the parturition of the higher animals."
My example, lungs, was in the context of tetrapod evolution. There's a rather nice series of fossils demonstrating the links between early amphibians and almost-as-early four-legged vertebrates, in this post by afarensis. That story also gives a nice example of the predictive power of evolutionary theory. Tiktaalik roseae was found because scientists working in that area knew that amphibians could be found in rocks of a particular age & early tetrapods in somewhat younger rocks. They predicted that an intermediate species might be found in rocks of intermediate age, identified a likely locality, went fossil hunting, and bingo!
Anyway, one of the big problems with life on land is that gas exchange becomes rather more complicated. While there's much more oxygen in air than in water, getting it is in some ways more difficult. Gas exchange surfaces need to be moist, but gills or skin, for example, would dry out very quickly if exposed to the air for too long. And in any case gills are useless as a gas exchange surface in air - their fine filamentous structure must be supported by water or it collapses into a thick clumpy mass with relatively little surface area exposed to the 'respiratory medium' (shorthand for the oxygen-bearing air or water). And for an animal testing the air, as it were, half a lung is not going to be good enough.
Now, we know that lungs originated as outpocketings from the gut - they're lined with the same endodermal tissues. The thing is, when did this happen and what sort of selection pressures might have been operating? The 'when' seems to have been a looong time ago, as lungs & lung derivatives - swim bladders - are found in all bony fish lineages, & bony fish first appear in the fossil record back in the Devonian. (It's more likely that lungs evolved in the common ancestor of all those modern fish groups, than that they all evolved them independently.)
The current hypothesis for the origin of lungs is that they probably evolved in Devonian fish living in ponds or shallow lagoons. Geological evidence indicates that there were alternating wet & dry seasons back then &, just as today, during the dry weather water levels would drop & conditions in them would become hypoxic (low in oxygen). Fish able to gulp air at the surface, and sequester it somewhere in the gut, would be at a selective advantage in these conditions (& before someone comes along & says, this is just a just-so story, remember that there are modern fish able to do this, holding their gulped bubbles of air in the mouth or somewhere along the intestine, whence oxygen can diffuse into the bloodstream). Any increase in size of the bubble-holding part of the gut - which from the position of lungs/swim bladders in living species must have been in a ventral outpocketing from the foregut - would have been selected for, as would any increase in the capillary beds associated with the nascent lung.
(And of course, that has landed us with a whole lot of problems further down the line - because the paths of food and air must cross at the back of the pharynx, something that brings with it the ever-present risk of choking. One of the hallmarks of evolution is that it optimises, rather than producing perfection.)
Lewis Held (2009) Quirks of human anatomy: an evo-devo look at the human body. Cambridge University Press. ISBN 978-0-511-59384-0 (e-book, Kindle edition)