Human cooperation remains a puzzle because it persists even in contexts where traditional theories predict it should not do so (i.e. among unrelated strangers, who never meet again and where reputation effects are absent). The leading explanation argues that cooperation occurs only if non-cooperators are punished. However, punishment is costly, so "second-order" non-cooperators may arise who defect from contributing to punishment, thus unravelling this solution. We propose an alternative: during our history, the fear of supernatural punishment (whether real or not) deterred defectors and may therefore represent an adaptive trait favoured by natural selection. Supernatural beliefs are universal among human societies, commonly connected to taboos for public goods, so it seems plausible that they serve an important function in fostering cooperation. This hypothesis offers an explanation for (a) geographic variation in religious practices as solutions to local cooperation problems; and (b) the power of political appeals to religion to elicit cooperation.