Scholars have debated naturalistic theories of religion for thousands of years, but only recently have scientists begun to test predictions empirically. Existing databases contain few variables on religion, and are subject to Galton's Problem because they do not sufficiently account for the non-independence of cultures or systematically differentiate the traditional states of cultures from their contemporary states. Here we present Pulotu: the first quantitative cross-cultural database purpose-built to test evolutionary hypotheses of supernatural beliefs and practices. The Pulotu database documents the remarkable diversity of the Austronesian family of cultures, which originated in Taiwan, spread west to Madagascar and east to Easter Island-a region covering over half the world's longitude. The focus of Austronesian beliefs range from localised ancestral spirits to powerful creator gods. A wide range of practices also exist, such as headhunting, elaborate tattooing, and the construction of impressive monuments. Pulotu is freely available, currently contains 116 cultures, and has 80 variables describing supernatural beliefs and practices, as well as social and physical environments. One major advantage of Pulotu is that it has separate sections on the traditional states of cultures, the post-contact history of cultures, and the contemporary states of cultures. A second major advantage is that cultures are linked to a language-based family tree, enabling the use phylogenetic methods, which can be used to address Galton's Problem by accounting for common ancestry, to infer deep prehistory, and to model patterns of trait evolution over time. We illustrate the power of phylogenetic methods by performing an ancestral state reconstruction on the Pulotu variable "headhunting", finding evidence that headhunting was practiced in proto-Austronesian culture. Quantitative cross-cultural databases explicitly linking cultures to a phylogeny have the potential to revolutionise the field of comparative religious studies in the same way that genetic databases have revolutionised the field of evolutionary biology.