i sometimes wonder what it was to live in early human times and make sense of everything: time, phenomena etc. i am not religious but i guess back then i would have ascribed anything to gods
I'm no anthropologist but religion must've started in parallel with verbal communication, storytelling, various degrees of higher level thinking.
That said, cave paintings, which are arguably the earliest "documentation" we have of human activity and their thoughts, depict pretty tangible things; pictures of animals, hand prints, people hunting animals, plants? that kind of thing. The earliest religious symbols may have been venus statues, but it seems that it cannot be concluded definitively whether they were objects of worship / depictions of deities. That said, there's clear signs of shamanic religion dating from the upper paleolithic, 50.000 years BC and onwards. https://en.wikipedia.org/wiki/Prehistoric_religion is a good read.
Anyway, ~52.000 years ago is still fairly recent, given homo sapiens emerged ~300.000 years ago and the earliest stone tools were from ~3.3 million years ago.
Personally, I think religion / the concept of gods or a higher power has been a part of humanity for as long as we've had the ability to think smort thoughts and communicate with one another. Some would be grounded in reality - good weather means good times - but others in myth, like the stars/moon, thunderstorms, etc.