Traditional investigations of the evolution of human social and political institutions trace their ancestry back to nineteenth century social scientists such as Herbert Spencer, and have concentrated on the increase in socio-political complexity over time. More recent studies of cultural evolution have been explicitly informed by Darwinian evolutionary theory and focus on the transmission of cultural traits between individuals. These two approaches to investigating cultural change are often seen as incompatible. However, we argue that many of the defining features and assumptions of ‘Spencerian’ cultural evolutionary theory represent testable hypotheses that can and should be tackled within a broader ‘Darwinian’ framework. In this paper we apply phylogenetic comparative techniques to data from Austronesian-speaking societies of Island South-East Asia and the Pacific to test hypotheses about the mode and tempo of human socio-political evolution. We find support for three ideas often associated with Spencerian cultural evolutionary theory: (i) political organization has evolved through a regular sequence of forms, (ii) increases in hierarchical political complexity have been more common than decreases, and (iii) political organization has co-evolved with the wider presence of hereditary social stratification.