Compared to dinosaurs, mammoths and saber-toothed cats, fish evolution may not seem all that interesting--until you realize that if it weren't for prehistoric fish, dinosaurs, mammoths and saber-toothed cats would never have existed. The first vertebrates on the planet, fish provided the basic "body plan" subsequently elaborated on by hundreds of millions of years of evolution: in other words, your great-great-great (multiply by a billion) grandmother was a small, meek fish of the Devonian period. (See a gallery of prehistoric fish pictures.)
The Earliest Vertebrates: Pikaia and Pals
Although most paleontologists wouldn't recognize them as true fish, the first fish-like creatures to leave an impression on the fossil record appeared during the middle Cambrian period, about 530 million years ago. The most famous of these, Pikaia, looked more like a worm than a fish, but it had four features crucial to later fish (and vertebrate) evolution: a head distinct from its tail, bilateral symmetry (the left side of its body looked like the right side), V-shaped muscles, and most importantly, a nerve cord running down the length of its body. Because this cord wasn't protected by a tube of bone or cartilage, Pikaia was technically a "chordate" rather than a vertebrate, but it still lay at the root of the vertebrate family tree.
Two other Cambrian proto-fish were a bit more robust than Pikaia. Haikouichthys is considered by some experts--at least those not overly concerned by its lack of a calcified backbone--to be the earliest jawless fish, and this inch-long creature had rudimentary fins running along the top and bottom of its body. The similar Myllokunmingia was slightly less elongated than either Pikaia or Haikouichthys, and it also had pouched gills and (possibly) a skull made of cartilage. (Other fish-like creatures may have predated these three genera by tens of millions of years; unfortunately, they haven't left any fossil remains.)
The Evolution of Jawless Fish
During the Ordovician and Silurian periods--from 490 to 410 million years ago--the world's oceans, lakes and rivers were dominated by jawless fish, so named because they lacked lower jaws (and thus the ability to consume large prey). You can recognize most of these prehistoric fish by the "-aspis" (the Greek word for "shield") in the second parts of their names, which hints at the second main characteristic of these early vertebrates: their heads were covered by tough plates of bony armor.
The most notable jawless fish of the Ordovician period were Astraspis and Arandaspis, six-inch-long, big-headed, finless fish that resembled giant tadpoles. Both of these species made their living by bottom-feeding in shallow waters, wriggling slowly above the surface and sucking up tiny animals and the waste of other marine creatures. Their Silurian descendants shared the same body plan, with the important addition of forked tail fins, which gave them more maneuverability.
If the "-aspis" fish were the most advanced vertebrates of their time, why were their heads covered in bulky, un-hydrodynamic armor? The answer is that, hundreds of millions of years ago, vertebrates were far from the dominant life forms in the earth's oceans, and these early fish needed a means of defense against giant "sea scorpions" and other large arthropods.
The Big Split: Lobe-Finned Fish, Ray-Finned Fish and Placoderms
By the start of the Devonian period--about 420 million years ago--the evolution of prehistoric fish veered off in two (or three, depending on how you count them) directions. One development, which wound up going nowhere, was the appearance of the jawed fishes known as placoderms ("plated skin"), the earliest identified example of which is Entelognathus. These were essentially larger, more varied "-aspis" fish with true jaws, and the most famous genus by far was the 30-foot-long Dunkleosteus, one of the biggest fish that ever lived.
Perhaps because they were so slow and awkward, placoderms vanished by the end of the Devonian period, outclassed by two other newly evolved families of jawed fish: the chondrichthians (fish with cartilaginous skeletons) and osteichthyans (fish with bony skeletons). The chondrichthians included prehistoric sharks, which went on to tear their own bloody path through evolutionary history. The osteichthyans, meanwhile, split into two further groups: the actinopterygians (ray-finned fish) and sarcopterygians (lobe-finned fish).
Ray-finned fish, lobe-finned fish, who cares? Well, you do: the lobe-finned fishes of the Devonian period, such as Panderichthys and Eusthenopteron, had a characteristic fin structure that enabled them to evolve into the first tetrapods--the proverbial "fish out of water" ancestral to all land-living vertebrates, including humans. The ray-finned fish stayed in the water, but went on to become the most successful vertebrates of all: today, there are tens of thousand of species of ray-finned fish, making them the most diverse and numerous vertebrates on the planet (among the earliest ray-finned fish were Saurichthys and Cheirolepis).
The Giant Fish of the Mesozoic Era
No history of fish would be complete without mentioning the giant "dino-fish" of the Triassic, Jurassic and Cretaceous periods (though these fish weren't as numerous as their oversized dinosaur cousins). The most famous of these giants were the Jurassic Leedsichthys, which some reconstructions put at a whopping 70 feet long, and the Cretaceous Xiphactinus, which was "only" about 20 feet long but at least had a more robust diet (other fish, compared to Leedsichthys' diet of plankton and krill). A new addition is Bonnerichthys, yet another large, Cretaceous fish with a tiny, protozoan diet.
Bear in mind, though, that for every "dino-fish" like Leedsichthys there are a dozen smaller prehistoric fish of equal interest to paleontologists. The list is nearly endless, but examples include Dipterus (an ancient lungfish), Enchodus (also known as the "saber-toothed herring"), the prehistoric rabbitfish Ischyodus, and the small but prolific Knightia, which has yielded so many fossils that you can buy your own for less than a hundred bucks.