The human protein arginine methyltransferase NDUFAF7 controls the assembly of the ∼1-MDa mitochondrial complex I (CI; the NADH ubiquinone oxidoreductase) by methylating its subunit NDUFS2. We determined crystal structures of MidA, the Dictyostelium ortholog of NDUFAF7. The MidA catalytic core domain resembles other eukaryotic methyltransferases. However, three large core loops assemble into a regulatory domain that is likely to control ligand selection. Binding of MidA to NDUFS2 is weakened by methylation, suggesting a mechanism for methylation-controlled substrate release. Structural and bioinformatic analyses support that MidA and NDUFAF7 and their role in CI assembly are conserved from bacteria to humans, implying that protein methylation already existed in proteobacteria. In vivo studies confirmed the critical role of the MidA methyltransferase activity for CI assembly, growth, and phototaxis of Dictyostelium. Collectively, our data elucidate the origin of protein arginine methylation and its use by MidA/NDUFAF7 to regulate CI assembly.