Frogs have the least understood fossil record of all major vertebrate groups in Australia. Here we report on pelvic remains of three Pleistocene frog species from the Nullarbor Plain, a large region of Australia where no living or fossil frogs had previously been discovered. One ilium, characterised by a small acetabular fossa with an indistinct peripheral rim, a broad dorsal prominence and enlarged supra-acetabular zone, is recognised here as representative of a new species of hylid, Litoria lundeliusi sp. nov. Three other ilia bear the hallmark generic attributes of the small myobatrachid Pseudophryne, two species of which co-occur today over much of southwestern Australia. A second larger myobatrachid is the best represented of the three species, and its ilial morphology matches that of the extant Neobatrachus sudelli. All three species were present in the early Pleistocene, but only N. sudelli is recorded in the middle Pleistocene. The loss of Litoria and Pseudophryne would be consistent with the disappearance of significant bodies of free water from the region, but the cause of the apparent extirpation of N. sudelli, which inhabits arid parts of Australia today, remains a mystery.