The old endemic rodents of Australia and New Guinea (Sahul) represent one or more large adaptive radiations including novel morphological adaptations to aquatic, arboreal, hopping, and arid ecologies. Four tribes recognized among the Sahulian old endemics (Hydromini, Conilurini, Anisomyini, and Uromyini) reflect distinct biogeographic and ecomorphological hypotheses about diversification within the Old Endemics. We present the first character-based phylogeny of the Sahulian Old Endemic rodents with broad sampling, nested within a broader phylogeny of the Murinae. We estimated phylogenies from >2,500 nucleotides of mtDNA sequence and >9,500 nucleotides from six autosomal nuclear loci, for individual genes and for the full concatenated data using parsimony, likelihood, and Bayesian methods. Our results strongly supported monophyly of the group and its sister relationship to the Philippine old endemics of the Chrotomys division. Most striking was the rapid diversification after the Late Miocene or Early Pliocene colonization of New Guinea from the west, consistent with a single colonization of the Sahulian continent. That was followed 2-3 My later by a second adaptive radiation resulting from one or more colonizations of Australia. Monophyly was not supported for the Anisomyini or the Conilurini but was for the Uromyini nested within the Conilurini and for the Hydromyini. Conflict among gene phylogenies was weak, and support for the consensus topology increased with more (even conflicting) data.