Understanding the evolution of Australia's extinct marsupial megafauna has been hindered by a relatively incomplete fossil record and convergent or highly specialized morphology, which confound phylogenetic analyses. Further, the harsh Australian climate and early date of most megafaunal extinctions (39-52 ka) means that the vast majority of fossil remains are unsuitable for ancient DNA analyses. Here, we apply cross-species DNA capture to fossils from relatively high latitude, high altitude caves in Tasmania. Using low-stringency hybridization and high-throughput sequencing, we were able to retrieve mitochondrial sequences from two extinct megafaunal macropodid species. The two specimens, Simosthenurus occidentalis (giant short-faced kangaroo) and Protemnodon anak (giant wallaby), have been radiocarbon dated to 46-50 and 40-45 ka, respectively. This is significantly older than any Australian fossil that has previously yielded DNA sequence information. Processing the raw sequence data from these samples posed a bioinformatic challenge due to the poor preservation of DNA.We explored several approaches in order to maximize the signal-to-noise ratio in retained sequencing reads. Our findings demonstrate the critical importance of adopting stringent processing criteria when distant outgroups are used as references for mapping highly fragmented DNA. Based on the most stringent nucleotide data sets (879 bp for S. occidentalis and 2,383 bp for P. anak), total-evidence phylogenetic analyses confirm that macropodids consist of three primary lineages: Sthenurines such as Simosthenurus (extinct short-faced kangaroos), the macropodines (all other wallabies and kangaroos), and the enigmatic living banded hare-wallaby Lagostrophus fasciatus (Lagostrophinae). Protemnodon emerges as a close relative of Macropus (large living kangaroos), a position not supported by recent morphological phylogenetic analyses.