The five macromolecular complexes that jointly mediate oxidative phosphorylation (OXPHOS) in mitochondria consist of many more subunits than those of bacteria, yet, it remains unclear by which evolutionary mechanism(s) these novel subunits were recruited. Even less well understood is the structural evolution of mitochondrial ribosomes (mitoribosomes): while it was long thought that their exceptionally high protein content would physically compensate for their uniquely low amount of ribosomal RNA (rRNA), this hypothesis has been refuted by structural studies. Here, we present a cryo-electron microscopy structure of the 73S mitoribosome from Neurospora crassa, together with genomic and proteomic analyses of mitoribosome composition across the eukaryotic domain. Surprisingly, our findings reveal that both structurally and compositionally, mitoribosomes have evolved very similarly to mitochondrial OXPHOS complexes via two distinct phases: A constructive phase that mainly acted early in eukaryote evolution, resulting in the recruitment of altogether approximately 75 novel subunits, and a reductive phase that acted during metazoan evolution, resulting in gradual length-reduction of mitochondrially encoded rRNAs and OXPHOS proteins. Both phases can be well explained by the accumulation of (slightly) deleterious mutations and deletions, respectively, in mitochondrially encoded rRNAs and OXPHOS proteins. We argue that the main role of the newly recruited (nuclear encoded) ribosomal-and OXPHOS proteins is to provide structural compensation to the mutationally destabilized mitochondrially encoded components. While the newly recruited proteins probably provide a selective advantage owing to their compensatory nature, and while their presence may have opened evolutionary pathways toward novel mitochondrion-specific functions, we emphasize that the initial events that resulted in their recruitment was non-adaptive in nature. Our framework is supported by population genetic studies, and it can explain the complete structural evolution of mitochondrial ribosomes and OXPHOS complexes, as well as many observed functions of individual proteins.