A long, long time ago when humans were settling down, domesticating crops and animals for food, they soon found they could produce a surplus. If they banded together in a commune, maybe if one of them had a bad year, the others could help support the misfortunate one.
Of course, occasionally they all had a bad year. Who's fault could this be? Most of them had worked very hard to bring in crops and tend their herds. It must have been an evil 'spirit/god/devil/etc' who was displeased with the commune's prosperity, or perhaps some other factor.
Any number of things could have displeased this 'spirit'. The boom in population that the humans had in a good harvest year, the overconsumption that they normally indulged in at harvest time, or the lack of general respect for the 'spirit'.
So the people now respect this 'spirit' as a powerful force to be dealt with. They can't see it, so they can't kill it. They have to appease the 'spirit'. One of the members of the commune would come up with this idea, and would have to find a way to please the 'spirit' to make it stop hurting the commune. The first priest.
The priest would suggest sacrificing excess foodstuffs, and limiting the procreational urge of the populace to appease the 'spirit'.
It would occur to the priest that the same famine hadn't happened in the neighboring vally, where there was another commune much the same. He would consider that the 'spirit' might have been sent by them to do his people harm.
The Christians may have been peddling their faith for 2000 years, but the idea's behind that faith started long before that. Christianity separated from Judaism, and Judaism pulled its original believers from a primitive, superstitious culture that worshiped and feared many natural events.
Since the events often happened at the worse possible time, and despite the fact that otherwise this culture would be enjoying itself, they rationalized that these events must be caused by a sentient being that didn't like them to enjoy themselves too much. Methods to appease these sentients included abstinence, fasting, prayer, sacrifice, etc.
At first, worship was on a village or community level. Once priests were able to practice their profession as their sole art (as opposed to having to farm with the rest of the bunch), they could proceed to excercise control over the populace, moving it in the dirrection of growth. Naturally, conflicts with neighboring tribes would take place, with involved tribes entreating their 'gods' to protect themselves, and do harm to the enemy.
Eventually, as one tribe began to dominate, their only accepted 'god' would become the God we've all come to not quite fully believe in today.