For production of proteins that are encoded by the mitochondrial genome, mitochondria rely on their own mitochondrial translation system, with the mitoribosome as its central component. Using extensive homology searches, we have reconstructed the evolutionary history of the mitoribosomal proteome that is encoded by a diverse subset of eukaryotic genomes, revealing an ancestral ribosome of alpha-proteobacterial descent that more than doubled its protein content in most eukaryotic lineages. We observe large variations in the protein content of mitoribosomes between different eukaryotes, with mammalian mitoribosomes sharing only 74 and 43% of its proteins with yeast and Leishmania mitoribosomes, respectively. We detected many previously unidentified mitochondrial ribosomal proteins (MRPs) and found that several have increased in size compared to their bacterial ancestral counterparts by addition of functional domains. Several new MRPs have originated via duplication of existing MRPs as well as by recruitment from outside of the mitoribosomal proteome. Using sensitive profile-profile homology searches, we found hitherto undetected homology between bacterial and eukaryotic ribosomal proteins, as well as between fungal and mammalian ribosomal proteins, detecting two novel human MRPs. These newly detected MRPs constitute, along with evolutionary conserved MRPs, excellent new screening targets for human patients with unresolved mitochondrial oxidative phosphorylation disorders.