Yep! I'll just address China but surely others can speak to other parts of the world.
One of the most famous early palaeontologists (if we want to call him that) is Shěn Kuò (沈括) who 'lived during the (Northern) Song (11th century). He developed theories of climate change and geomorphology, all because of fossils.
For climate change, this was due to the discovery of fossilised bamboo in areas of Northern Shǎnxi 陝西 (not Shānxī 山西) where bamboo didn't grow at the time, but clearly had in the past. This was after a landslide in Yánzhōu 延州, in an area called Yǒngníng-guān 永寧關, exposed the fossils.
For his theories on geomorphology (how landforms develop), he had come across fossils of marine life in places far from any seas. This was in the Tàiháng mountain range (太行山) around Shānxī 山西 near Zézhōu 澤州, Jìnchéng 晉城. The fossil was of a kind of water snake, and while Shěn Kuò didn't discover it himself. An "ignorant villager" ("村民無知") had discovered it and was terrified that he then tried to destroy it. Shěn had heard about it, asked for a piece (which he recieved) and then worked out what had been found. At the time, fossils of crabs ("石蟹之類") had already been known to Shěn, and he likened the snake fossil to those in his writings, though he did not expand on the other known fossils.
Shěn wrote about all this in a book of essays entitled mèng xī bǐ tán (夢溪筆談), usually translated in English as Dream Pool Essays (not that that's a very descriptive name), which he wrote in his later. It's available in English translation. The full passage about both cases is here in case anyone reads Chinese. I'm bad at translating so I'll just leave it here in case others find it useful:
近歲延州永寧關大河岩崩敗地數十尺，土下得竹筍一林，凡數百莖，根幹相連，悉化為石。適有中人過，亦取數莖去，雲欲進呈。延郡素無竹，此入在數十尺土下，不知其何代物。無乃曠古以前，地卑氣濕而宜竹耶？
婺州金華山有松石，又如核桃、蘆根、蛇蟹之類，皆有成石者；然皆其地本有之物，不足深怪。此深地中所無，又非本土所有之物，物可異耳。
治平中，澤州人家穿井，土中見一物，蜿蜿如龍蛇。大畏之，不敢角，久之，見其不動，試摸之，乃石也。村民無知，遂碎之，時程伯純為晉城令，求得一段，鱗甲皆如生物。蓋蛇蜃所化，如石蟹之類
The middle part is regarding similar fossils which were also already known in other parts of China, but as I said there's not much detail about them. However since things like petrified wood aren't exactly rare in the world I think we can assume at least some of them are exactly that kind of thing.
Source:
(edited to fix for formatting)
I wrote about this recently, so I'll just copy and paste my earlier answer. The people of Mesoamerica had discovered dinosaur bones, but they thought that the bones were the bones of giants. This account is from Bernal Diaz, a soldier who fought with Cortes in conquering the Aztecs: "The Aztecs said that their ancestors told them that a long time ago there were settlements of men and women who were very tall with huge bones; that because they were very evil and of bad behavior, they killed them fighting with them, and those remaining died. And in order that we could see what enormous bodies they had, they brought a leg bone of one of them, and it was very heavy and very large in height compared to a man of average stature. And that leg bone was from the knee to the hip. I measured myself with it and it was as tall as I, although I am of average height. And they brought other bones like the first. Most were already bare and hardened from the earth, and all of us marveled at seeing those leg bones, and we were certain that there had been giants in this country. And our Captain Cortes told us that he would be sending that great bone to Spain in order that His Majesty could see it, and so thus we sent it with the first products that went out."