The sacred texts of five world religions (Buddhism, Christianity, Hinduism, Islam, and Judaism) use similar belief systems to set limits on sexual behavior. We propose that this similarity is a shared cultural solution to a biological problem: namely male uncertainty over the paternity of offspring. Furthermore, we propose the hypothesis that religious practices that more strongly regulate female sexuality should be more successful at promoting paternity certainty. Using genetic data on 1,706 father-son pairs, we tested this hypothesis in a traditional African population in which multiple religions (Islam, Christianity, and indigenous) coexist in the same families and villages. We show that the indigenous religion enables males to achieve a significantly (P = 0.019) lower probability of cuckoldry (1.3% versus 2.9%) by enforcing the honest signaling of menstruation, but that all three religions share tenets aimed at the avoidance of extrapair copulation. Our findings provide evidence for high paternity certainty in a traditional African population, and they shed light on the reproductive agendas that underlie religious patriarchy.