While the crocodyliform lineage extends back over 200 million years (Myr) to the Late Triassic, modern forms—members of Eusuchia—do not appear until the Cretaceous. Eusuchia includes the crown group Crocodylia, which comprises Crocodyloidea, Alligatoroidea and Gavialoidea. Fossils of non-crocodylian eusuchians are currently rare and, in most instances, fragmentary. Consequently, the transition from Neosuchia to Crocodylia has been one of the most poorly understood areas of crocodyliform evolution. Here we describe a new crocodyliform from the mid-Cretaceous (98–95 Myr ago; Albian–Cenomanian) Winton Formation of Queensland, Australia, as the most primitive member of Eusuchia. The anatomical changes associated with the emergence of this taxon indicate a pivotal shift in the feeding and locomotor behaviour of crocodyliforms—a shift that may be linked to the subsequent rapid diversification of Eusuchia 20 Myr later during the Late Cretaceous and Early Tertiary. While Laurasia (in particular North America) is the most likely ancestral area for Crocodylia, the biogeographic events associated with the origin of Eusuchia are more complex. Although the fossil evidence is limited, it now seems likely that at least part of the early history of Eusuchia transpired in Gondwana.