| Paleontology is only a recent science in its current, formalised sense. However, it has existed in one form or another for almost the entire span of mankind.
Neanderthal man placed fossils around their dead in burials, perhaps attributing them with a magic that would defy death: these rocks, the hardest and most formidible substance in their world contained the images of creatures which have achieved the immortality of preservation in stone. Death was no longer able to reach them.
The first people to record their speculations on these strange rocks that took the form of plants and animals were Greek philosophers. The oldest recorded statement that suggested fossils may be the remains of once-living creatures was made by Xanthos of Sardis in about 500 B.C.
Aristotle (384 B.C.) suggested that fossils of fish were remnants of sea animals that swam into cracks in rocks, and were stranded there. These early speculations were held for more than 2000 years, with no improvements or additions to these theories. In this time, the Roman civilization surpassed that of the Greeks, and itself passed into the intellectual night of the Dark Ages.
During the Middle Ages and the Renaissance, fossils were illustrated and described as figured stones by the most learned people of the time, doctors and clerics. In these religious times, the origin of these figured stones was a matter of great dispute. Some attributed them to the workings of some strange force deep inside of the Earth, others to the evil machinations of the Devil, and still others thought they had fallen from the sky as thunderbolts during storms or as falling stars. As a side-note, some scholars believe that this may be an indicator of early meteor impacts which contained some kind of fossil record.
The starlike patterns of certain fossils, such as crinoids and corals suggested the sky as their source: subsequently, these were called Star Stones.
By the middle of the eighteenth century, the similarity of fossils to some currently living organisms had convinced many naturalists that these mysterious stones were the remains of plants and animals that had somehow been preserved within rocks.
The more perceptive of these put forward the idea that the sea must have once covered larger areas in order for marine fossils to be deposited so far inland. Most people at the time attributed them to the Biblical Flood: however, palentologists during the early nineteenth century discovered evidence which caused the flood theory to fold. A succession of sedimentary rocks revealed a progression of lifeforms which could not be the result of a single catastrophe: the ages of the sedimentary beds meant that the fossils had been formed over periods covering tens of thousands, if not millions of years!
By the beginning of the nineteenth century, the controversy was over. The consensus was that fossils were remnants of organisms that had lived in the distant past. The groundwork had been laid for the recognition of fossils as evidence of evolution.
Note: I've intentionally used the North American spelling of Paleontology vs. Palaeontology to make referencing this and related nodes easier. | 
