I have read a little of what paleo anthropologists have written about this, take it as you will, it is not as if they were actually there or anything.
What they believe is that having some form of 'belief' or 'faith' played a key role in holding together the kinds of small bands our distant ancestors lived in. What did they believe? Well we know that they took the trouble to bury their dead, often with flowers or other things,and that fairly soon after they became people as we would recognise them they created paintings and played music, they have found flutes and drums that are tens of thousands of years old made of bone. Now to me at least, the mindset required to play music can not have changed that much, perhaps they thought about the same sorts of things that we do?