MnmE and GidA are involved in the modification of wobble uridine to carboxymethylaminomethyl uridine in certain tRNAs. Malfunctioning of the human orthologs has been implicated in mitochondrial diseases. MnmE is a conserved G protein activated by dimerization. Here, we show that complex formation between MnmE and GidA involves large conformational changes that induce G-domain dimerization of MmnE and that GidA co-stimulates GTP hydrolysis on MnmE. Starting from a structural model of the complex, we identify interface mutations disrupting complex formation or communication. Although GidA does not directly contact the G-domains, conformational changes in MnmE, induced by G-domain dimerization in the triphosphate state, regulate the affinity for GidA. We developed a tRNA modification assay and demonstrate for the first time in vitro that the MnmE/GidA complex catalyzes incorporation of glycine into tRNA. An intact MnmE/GidA complex rather than their sequential action is crucial for in vitro modification. Since only GTP, but not GDP or non-hydrolyzable GTP analogs, drives the MnmE/GidA-catalyzed modification reaction, we conclude that GTP hydrolysis is essential for activity. We finally show that an active GTPase, an intact MnmE/GidA communication, and dimerization of G-domains are necessary for in vivo functioning since mutations disrupting either result in a respiratory deficient phenotype in yeast.