Recent studies of the evolution of religion have revealed the cognitive underpinnings of belief in supernatural agents, the role of ritual in promoting cooperation, and the contribution of morally punishing high gods to the growth and stabilization of human society. The universality of religion across human society points to a deep evolutionary past. However, specific traits of nascent religiosity, and the sequence in which they emerged, have remained unknown. Here we reconstruct the evolution of religious beliefs and behaviors in early modern humans using a global sample of hunter-gatherers and seven traits describing hunter-gatherer religiosity: animism, belief in an afterlife, shamanism, ancestor worship, high gods, and worship of ancestors or high gods who are active in human affairs. We reconstruct ancestral character states using a time-calibrated supertree based on published phylogenetic trees and linguistic classification and then test for correlated evolution between the characters and for the direction of cultural change. Results indicate that the oldest trait of religion, present in the most recent common ancestor of present-day hunter-gatherers, was animism, in agreement with long-standing beliefs about the fundamental role of this trait. Belief in an afterlife emerged, followed by shamanism and ancestor worship. Ancestor spirits or high gods who are active in human affairs were absent in early humans, suggesting a deep history for the egalitarian nature of hunter-gatherer societies. There is a significant positive relationship between most characters investigated, but the trait "high gods" stands apart, suggesting that belief in a single creator deity can emerge in a society regardless of other aspects of its religion.