Mitochondria are ATP-generating organelles whose endosymbiotic origin has been a key event in the evolution of eukaryotic cells. Despite overwhelming phylogenetic evidence for an alphaproteobacterial ancestry, efforts to pinpoint the closest relatives among the sampled alphaproteobacteria have been conflicting, complicating detailed inferences about the identity and nature of the mitochondrial ancestor. While most studies support that mitochondria evolved from an ancestor related to Rickettsiales, an order that includes several host-associated pathogenic and endosymbiotic lineages, others suggest that mitochondria evolved from a free-living group. Here we re-evaluate the phylogenetic placement of mitochondria. We employ genome-resolved binning of oceanic metagenome datasets and increase the genomic sampling of Alphaproteobacteria with twelve novel divergent clades, and one novel 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 prior to the divergence of all sampled alphaproteobacteria. In light of this new result, previous hypotheses on the nature of the mitochondrial ancestor should be re-evaluated.