The conceptual understanding of what constitutes a fossil did not come all formed, and mostly did not come from dinosaurial material. It had humbler beginnings.

Fossils of all types were found and known to several historical civilizitions. In particular, fossil shark teeth were quite common and reasonably well known throughout mediterranean societies; they were long believed to have magical properties and known as "tongue stones" (glossopetrae), but there was no widespread consensus on their nature, significance or origin. Other fossils such as shells and ammonites also had been noticed. They too were not well understood and a variety of interpretations were circulating.

One of the earliest attempts to suggest that fossils were preserved remains of previous organic life was made by Nicolaus Steno (1638-1686) in "Prodromus to a dissertation on a solid body naturally contained within a solid." Steno was mostly working from the perspective of fossil sharks teeth which he considered too similar to the teeth of modern shark heads he had dissected for them to be anything else. In this essay, Steno made the case for one of the basic principles of chronological relationships in geology where pre-existing objects were encased in geologcal materials, and thus older than the surrounding matrix (The new category of object was defined as "a solid within a solid", hence the name of his prodromus). This concept was made in opposition to processes of void filling (such as geodes, and like that). He also established the principle of superposition, the principle of horizontality and the principle of continuity, all of which formed the basis for the science of stratigraphy.

For further reading, you may want to have a look at S J Gould's essay on this conceptual revolution (S.J. Gould, 1983. "The titular bishop of Titiopolis", in: "Hen's teeth and horses toes", WW Norton & Company)