ABSTRACT: Two main theories have been put forward to explain the origin of mitochondria in eukaryotes: phagotrophic engulfment (undigested food) and microbial symbiosis (physiological interactions). The two theories generate mutually exclusive predictions about the order in which mitochondria and phagocytosis arose. To discriminate the alternatives, we have employed ancestral state reconstructions (ASR) for phagocytosis as a trait, phagotrophy as a feeding habit, the presence of mitochondria, the presence of plastids, and the multinucleated organization across major eukaryotic lineages. To mitigate the bias introduced by assuming a particular eukaryotic phylogeny, we reconstructed the appearance of these traits across 1789 different rooted gene trees, each having species from opisthokonts, mycetozoa, hacrobia, excavate, archeplastida, and Stramenopiles, Alveolates and Rhizaria. The trees reflect conflicting relationships and different positions of the root. We employed a novel phylogenomic test that summarizes ASR across trees which reconstructs a last eukaryotic common ancestor that possessed mitochondria, was multinucleated, lacked plastids, and was non-phagotrophic as well as non-phagocytic. This indicates that both phagocytosis and phagotrophy arose subsequent to the origin of mitochondria, consistent with findings from comparative physiology. Furthermore, our ASRs uncovered multiple origins of phagocytosis and of phagotrophy across eukaryotes, indicating that, like wings in animals, these traits are useful but neither ancestral nor homologous across groups. The data indicate that mitochondria preceded the origin of phagocytosis, such that phagocytosis cannot have been the mechanism by which mitochondria were acquired.