Based on the known fossil record, the majority of crocodylians from the Cenozoic Era of Australia are referred to the extinct clade Mekosuchinae. The only extant crocodylians in Australia are two species of Crocodylus. Hence, the viewpoint that Crocodylus and mekosuchines have been the only crocodylians inhabiting Australia during the Cenozoic has remained largely undisputed. Herein we describe Australia’s first tomistomine crocodylian, Gunggamarandu maunala gen. et sp. nov., thus challenging the notion of mekosuchine dominance during most of the Cenozoic. The holotype specimen of Gunggamarandu maunala derives from the Pliocene or Pleistocene of south-eastern Queensland, marking the southern-most global record for Tomistominae. Gunggamarandu maunala is known from a large, incomplete cranium that possesses a unique combination of features that distinguishes it from other crocodylians. Phylogenetic analyses place Gunggamarandu in a basal position within Tomistominae, specifically as a sister taxon to Dollosuchoides from the Eocene of Europe. These results hint at a potential ghost lineage between European and Australian tomistomines going back more than 50 million years. The cranial proportions of the Gunggamarandu maunala holotype specimen indicate it is the largest crocodyliform yet discovered from Australia.