Much of the higher-order phylogeny of eukaryotes is well resolved, but the root remains elusive. We assembled a dataset of 183 eukaryotic proteins of archaeal ancestry to test this root. The resulting phylogeny identifies four lineages of eukaryotes currently classified as "Excavata" branching separately at the base of the tree. Thus, Parabasalia appear as the first major branch of eukaryotes followed sequentially by Fornicata, Preaxostyla, and Discoba. All four excavate branch points receive full statistical support from analyses with commonly used evolutionary models, a protein structure partition model that we introduce here, and various controls for deep phylogeny artifacts. The absence of aerobic mitochondria in Parabasalia, Fornicata, and Preaxostyla suggests that modern eukaryotes arose under anoxic conditions, probably much earlier than expected, and without the benefit of mitochondrial respiration.