Coucals are large, predatory, primarily ground-dwelling cuckoos of the genus Centropus, with 26 extant species ranging from Africa to Australia. Their evolutionary and biogeographical history are poorly understood and their fossil record almost non-existent. Only one species (Centropus phasianinus) currently inhabits Australia, but there is now fossil evidence for at least three Pleistocene species. One of these (Centropus colossus) was described from south-eastern Australia in 1985. Here we describe additional elements of this species from the same site, and remains of two further extinct species from the Thylacoleo Caves of the Nullarbor Plain, south-central Australia. The skeletal morphology and large size of the three extinct species indicates that they had reduced capacity for flight and were probably primarily ground-dwelling. The extinct species include the two largest-known cuckoos, weighing upwards of 1 kg each. They demonstrate that gigantism in this lineage has been more marked in a continental context than on islands, contrary to the impression gained from extant species. The evolutionary relationships of the Australian fossil coucals are uncertain, but our phylogenetic analysis indicates a possible close relationship between one of the Nullarbor species and extant Centropus violaceus from the Bismarck Archipelago. The presence of three coucals in southern Australia markedly extends the geographical range of the genus from tropical Australia into southern temperate regions. This demonstrates the remarkable and consistent ability of coucals to colonize continents despite their very limited flying ability.