Fossils in general took a while to make sense of, and to even find threatening to religious views of the world. While they had been noticed throughout history much less was made of them than you'd imagine. Part of this is due to the fact that recognizing that what you have found is in fact a "giant lizard" is more difficult than you probably realize — you have to carefully dig up the fossil and separate out the pieces, you have to know about comparative anatomy (that is, you have to know a lizard skeleton when you see one, and know it is a lizard), and you have to understand that these rock skeletons were once bone skeletons that have undergone fossilization.

Generally speaking the 18th-century naturalist Georges Cuvier is credited for being the one who really put our understanding of fossils on a modern footing — that there was a world before ours, it involved very different creatures, it suffered from a great catastrophe that killed the great creatures, that the animals of the world can completely die out or disappear (extinction). Extinction itself is a rather profound and non-intuitive idea for people who felt that the animals of the world seemed unimaginably abundant. The idea that there was a world before ours filled with great and bizarre creatures was itself a pretty big jump. It is easy today to not realize how strange this would have looked, because we raise children with this understanding, so it seems obvious and natural to us. In the 18th century this was not the case.

Elizabeth Kolbert had a wonderful article about Cuvier in the New Yorker a few months back; unfortunately it is now subscriber-only. Her book The Sixth Extinction has just come out and I believe it contains a discussion of this as well (I would tell you for sure but my wife is hogging our copy of the book, because it is fascinating and well-done).

In the 19th century, fossils became routinely (and systematically) dug up, reconstructed, analyzed, and popularized. This is where the religious reaction became acute, in the age of evolutionary speculation. (Not just Darwin, but also Lamarck and especially Chambers, who paved the road for the Darwinian debates.)

You may be interested in the 'Historical views about fossils and dinosaurs' section of the Popular Questions pages - as found in the sidebar.

Even before dinosaurs became famous, there were still a number of ancient fossils being found for centuries prior to the 1800s.

Nicholas Steno was figuring out deep time stratigraphy in the 1600s. He was a genius at dissection and vivisection. He also connected "tongue stones" to having actually been shark's teeth.

http://en.wikipedia.org/wiki/Nicolas_Steno

http://evolution.berkeley.edu/evolibrary/article/0_0_0/history_04