Speech development, and changes in the brain as consciousness evolved, is suggested to have occurred around 3,000 years ago. Jaynes' Bicameral Mind is a theory that posits that the brain's two distinct hemispheres did not communicate and humans experienced auditory hallucinations in one half of the brain that they could not yet articulate via the other, separate half in undeveloped speech. As the brain evolved, so did language development and expression of conscious awareness. Jaynes and others suggest that primitive appreciation of human experiences of nature resulted in explanations like a god talking to humans when they were having auditory hallucinations, or causing sensational events that humans believed could only have been brought to them by a deity, when we now know that thngs like fires, floods and plagues can happen naturally.
I am sure there are many other alternative explanations for how primitive humans began to believe in the supernatural. Expansion of language did not occur in a vacuum and shared communication and understanding had to start somewhere. We are animals who have evolved at our own pace. It's now acknowledged that other animals have some degree of consciousness and even the beginnings of language that we don't yet understand.
Religion is a relatively recent phenomenon in the evolution of modern man. Worship of objects, the sun, the planets and the ocean were probably as vehement as worship of a god for our ancestors.