The phylogeny of eutherian mammals contains some of the most recalcitrant nodes in the tetrapod tree of life. We combined comprehensive taxon and character sampling to explore three of the most debated interordinal relationships among placental mammals. We performed in silico extraction of ultraconserved element (UCE) loci from 72 published genomes and in vitro enrichment and sequencing of UCEs from 28 additional mammals, resulting in alignments of 3,787 loci. We analyzed these data using concatenated and multispecies coalescent phylogenetic approaches, topological tests, and exploration of support among individual loci to identify the root of Eutheria and the sister groups of tree shrews (Scandentia) and horses (Perissodactyla). Individual loci provided weak, but often consistent support for topological hypotheses. Although many gene trees lacked accepted species-tree relationships, summary coalescent topologies were largely consistent with inferences from concatenation. At the root of Eutheria, we identified consistent support for a sister relationship between Xenarthra and Afrotheria (i.e., Atlantogenata). At the other nodes of interest, support was less consistent. We suggest Scandentia is the sister of Primatomorpha (Euarchonta), but we failed to reject a sister relationship between Scandentia and Glires. Similarly, we suggest Perissodactyla is sister to Cetartiodactyla (Euungulata), but a sister relationship between Perissodactyla and Chiroptera remains plausible.