Molecular phylogeneticists must frequently decide on a painful trade-off between the number of taxa and (tic number of sequences used in a study. Here, we illustrate the advantages of a method of combining quartet trees to solve this dilemma. We apply the method to a data set of 640 protein-sequence alignments from 4 to 24 eutherian taxa, and obtain a global eutherian phylogeny. In agreement with recent studies, we identify three major super-ordinal clades. The first clade is Afrotheria, a cluster of endemic African mammals. The second clade is an emended Laurasiatheria, consisting of Cetartiodactyla (cetaceans, ruminants, hippopotamuses, pigs, and tylopods), Perissodactyla (horses and rhinoceroses), Carnivora, Pholidota (pangolins), Chiroptera (bats), and Erinaceidae (hedgehogs). A tentatively identified third clade consists of some archontans (primates, flying lemurs, and tree shrews) as well as lagomorphs and rodents. Evolutionary relations within these major clades are well resolved. We also show that nuclear encoded proteins resolve eutherian phylogeny better than complete mitochondria. Finally, our results demonstrate that combining quartet trees provides a major opportunity to resolve unevenly sampled complex phylogenies.