The Cracticidae (Passeriformes) is an endemic Australo-Papuan family that, for the purposes of this paper, comprises the butcherbirds and Australian Magpie (Cracticus), currawongs (Strepera) and peltops (Peltops). Here we describe a new genus and species of cracticid from an Early Miocene deposit in the Riversleigh World Heritage Area, northwestern Queensland, Australia. Kurrartapu johnnguyeni, gen. nov., sp. nov. is described from a proximal tarsometatarsus that is similar in size to that of the extant Black Butcherbird (C. quoyi). This new species shares morphological features with the Strepera-Cracticus clade to the exclusion of Peltops, which suggests that it is a representative of the crown-group Cracticidae. Kurrartapu johnnguyeni represents the first Tertiary record of the Cracticidae in Australia, and is in concordance with molecular estimates for the timing of the cracticid radiation. We also describe morphological differences of the tarsometatarsus between cracticids and woodswallows (Artamus), which have at times been considered confamilial. We add this new cracticid to the expanding Tertiary fossil record of passerines in Australia, which plays a significant role in our understanding of early passerine evolution.