Obtaining a well supported schema of phylogenetic relationships among the major groups of living organisms requires considering as much taxonomic diversity as possible, but the computational cost of calculating large phylogenies has so far been a major obstacle. We show here that the parsimony algorithms implemented in TNT can successfully process the largest phylogenetic data set ever analysed, consisting of molecular sequences and morphology for 73 060 eukaryotic taxa. The trees resulting from molecules alone display a high degree of congruence with the major taxonomic groups, with a small proportion of misplaced species; the combined data set retrieves these groups with even higher congruence. This shows that tree-calculation algorithms effectively retrieve phylogenetic history for very large data sets, and at the same time provides strong corroboration for the major eukaryotic lineages long recognized by taxonomists.