Megapodes are unusual galliform birds that use passive heat sources to incubate their eggs. Evolutionary relationships of extant megapode taxa have become clearer with the advent of molecular analyses, but the systematics of large, extinct forms (Progura gallinacea, Progura naracoortensis) from the late Cenozoic of Australia has been a source of confusion. It was recently suggested that the two species of Progura were synonymous, and that this taxon dwarfed into the extant malleefowl Leipoa ocellata in the Late Pleistocene. Here, we review previously described fossils along with newly discovered material from several localities, and present a substantial taxonomic revision. We show that P. gallinacea and P. naracoortensis are generically distinct, describe two new species of megapode from the Thylacoleo Caves of south-central Australia, and a new genus from Curramulka Quarry in southern Australia. We also show that L. ocellata was contemporaneous with larger species. Our phylogenetic analysis places four extinct taxa in a derived clade with the extant Australo-Papuan brush-turkeys Talegalla fuscirostris, L. ocellata, Alectura lathami and Aepypodius bruijnii. Therefore, diversity of brush-turkeys halved during the Quaternary, matching extinction rates of scrubfowl in the Pacific. Unlike extant brush-turkeys, all the extinct taxa appear to have been burrow-nesters.