Bandicoots (Peramelemorphia) are a unique order of Australasian marsupials whose sparse fossil record has been used as prima facie evidence for climate change coincident faunal turnover. In particular, the hypothesized replacement of ancient rainforest-dwelling extinct lineages by antecedents of xeric-tolerant extant taxa during the late Miocene (~10 Ma) has been advocated as a broader pattern evident amongst other marsupial clades. Problematically, however, this is in persistent conflict with DNA phylogenies. We therefore determine the pattern and timing of bandicoot evolution using the first combined morphological + DNA sequence dataset of Peramelemorphia. In addition, we document a remarkably archaic new fossil peramelemorphian taxon that inhabited a latest Quaternary mosaic savannah-riparian forest ecosystem on the Aru Islands of Eastern Indonesia. Our phylogenetic analyses reveal that unsuspected dental homoplasy and the detrimental effects of missing data collectively obscure stem bandicoot relationships. Nevertheless, recalibrated molecular clocks and multiple ancestral area optimizations unanimously infer an early diversification of modern xeric-adapted forms. These probably originated during the late Palaeogene (30-40 Ma) alongside progenitors of other desert marsupials, and thus occupied seasonally dry heterogenous habitats long before the onset of late Neogene aridity.