Hydrogenotrophic methanogens possessing the hydrogen-dependent dehydrogenase Hmd also encode paralogs of this protein whose function is poorly understood. Here we present biochemical evidence that the two inactive Hmd paralogs of Methanocaldococcus jannaschii, HmdII and HmdIII, form binary and ternary complexes with several components of the protein translation apparatus. HmdII and HmdIII, but not the active dehydrogenase Hmd, bind with micromolar binding affinities to a number of tRNAs and form ternary complexes with tRNA(Pro) and prolyl-tRNA synthetase (ProRS). Fluorescence spectroscopy experiments also suggest that binding of HmdII and ProRS involves distinct binding determinants on the tRNA. These biochemical data suggest the possibility of a regulatory link between energy production and protein translation pathways that may allow a rapid cellular response to altered environmental conditions.