Mitochondria are ATP-generating organelles, the endosymbiotic origin of which was a key event in the evolution of eukaryotic cells¹ . Despite strong phylogenetic evidence that mitochondria had an alphaproteobacterial ancestry² , efforts to pinpoint their closest relatives among sampled alphaproteobacteria have generated conflicting results, complicating detailed inferences about the identity and nature of the mitochondrial ancestor. While most studies support the idea that mitochondria evolved from an ancestor related to Rickettsiales^3-9, an order that includes several host-associated pathogenic and endosymbiotic lineages^10,11, others have suggested that mitochondria evolved from a free-living group^12-14. Here we re-evaluate the phylogenetic placement of mitochondria. We used genome-resolved binning of oceanic metagenome datasets and increased the genomic sampling of Alphaproteobacteria with twelve divergent clades, and one clade representing a sister group to all Alphaproteobacteria. Subsequent phylogenomic analyses that specifically address long branch attraction and compositional bias artefacts suggest that mitochondria did not evolve from Rickettsiales or any other currently recognized alphaproteobacterial lineage. Rather, our analyses indicate that mitochondria evolved from a proteobacterial lineage that branched off before the divergence of all sampled alphaproteobacteria. In light of this new result, previous hypotheses on the nature of the mitochondrial ancestor^6,15,16 should be re-evaluated.