Bandicoots (Peramelemorphia) are a major order of australidelphian marsupials, which despite a fossil record spanning at least the past 25 million years and a pandemic Australasian range, remain poorly understood in terms of their evolutionary relationships. Many living peramelemorphians are critically endangered, making this group an important focus for biological and conservation research. To establish a phylogenetic framework for the group, we compiled a concatenated alignment of nuclear and mitochondrial DNA sequences, comprising representatives of most living and recently extinct species. Our analysis confirmed the currently recognised deep split between Macrotis (Thylacomyidae), Chaeropus (Chaeropodidae) and all other living bandicoots (Peramelidae). The mainly New Guinean rainforest peramelids were returned as the sister clade of Australian dry-country species. The wholly New Guinean Peroryctinae was sister to Echymiperinae. The poorly known and perhaps recently extinct Seram Bandicoot (Rhynchomeles) is sister to Echymipera. Estimates of divergence times from relaxed-clock Bayesian methods suggest that living bandicoots originated in the late Oligocene or early Miocene, much earlier than currently thought based on fossils. Subsequent radiations within Peramelemorphia probably took place on the Australian mainland during the Miocene, with diversification of rainforest taxa on the newly emergent New Guinean landmasses through the middle-late Miocene and complete establishment of modern lineages by the early Pliocene.