Ctenocephalides felis, the cat flea shown here, is a typical member of the Siphonaptera ("sucking-wingless"), the fleas. Although known to be related to the true flies (the Diptera) by details of internal structure, the Siphonaptera are highly modified for a parasitic existence; they have no wings and no compound eyes, the legs are modified for jumping, the antennae are very short and recessed in grooves on the head, and the body is highly flattened laterally. Most are parasites on mammals; a few live on birds. Adult fleas feed on blood, while their larvae feed on organic debris.
Fleas are extremely rare as fossils; their small size and specialized habitat makes them highly unlikely candidates for fossilization. Two species have been found in amber from the Baltic region (late Eocene-Oligocene); living members of the family of fleas to which these fossils belong (Hystrichopsyllidae) are mostly parasitic on insectivores (moles and shrews). A few Cretaceous fossils have been assigned to the Siphonaptera (e.g. Riek, 1970), but some of these fossils are questionable (Carpenter, 1992). Since the Siphonaptera are mostly parasitic on mammals, they presumably evolved at about the time the mammals were evolving, in the Jurassic and Cretaceous.
Researchers, and those who just can't get enough information on fleas, shoulddefinitely check out Flea News, a biennial newsletter put out by the Department of Entomology at Iowa State University.
Carpenter, F.M. 1992. Treatise on Invertebrate Paleontology. Part R: Arthropoda 4. Volume 4: Superclass Hexapoda. Geological Society of America and University of Kansas Press, Lawrence, Kansas.
Riek, E.F. 1970. Lower Cretaceous fleas. Nature 227: 746-747.
The Fleas Homepage of the Zoological Institue (St. Petersburg, Russia)