Our knowledge of early Australasian societies has significantly expanded in recent decades with more than 220 Pleistocene sites reported from a range of environmental zones and depositional contexts. The uniqueness of this dataset has played an increasingly important role in global debates about the origins and expression of complex behaviour among early modern human populations. Nevertheless, discussions of Pleistocene behaviour and cultural innovation are yet to adequately consider the effects of taphonomy and archaeological sampling on the nature and representativeness of the record. Here, we investigate the effects of preservation and sampling on the archaeological record of Sahul, and explore the implications for understanding early cultural diversity and complexity. We find no evidence to support the view that Pleistocene populations of Sahul lacked cognitive modernity or cultural complexity. Instead, we argue that differences in the nature of early modern human populations across the globe were more likely the consequence of differences in population size and density, interaction and historical contingency. Copyright © 2011 Elsevier Ltd. All rights reserved.