Our nature is necessary, but not sufficient, for religion. Religion wasn't invented by human hunter-gatherers; it only came around after the advent of farming, when we began to think in long timescales (like harvests, or winters) and had static resources (crops, houses) that had to be defended. Thus, we invented prayer to try to change the far future (i.e. long-term weather conditions—due to the large intervening period, it wasn't obvious whether it worked or not in any given instance, so we assumed it did), and commandments to justify our right to static resources, or our reasoning for pillaging them. We also invented the afterlife to explain how our feeling of consciousness would proceed into the far future, and gods to explain capricious phenomena (like lightning, or floods) that our minds instinctively anthropomorphized.
Hunter-gatherers had their own "natural" superstitions, such as the belief that opposing tribes and the unliked were capable of "witchcraft", but these were abductive reasoning, seeing effects and guessing at individual, short-timescale past causes, rather than inductive reasoning, seeing events and proposing prinicples that would explain/predict future events.