In the three domains of life, vitamin B12 (cobalamin) is primarily used in methyltransferase and isomerase reactions. The methyltransferase complex MtrA-H of methanogenic archaea has a key function in energy conservation by catalysing the methyl transfer from methyl-tetrahydromethanopterin to coenzyme M and its coupling with sodium-ion translocation. The cobalamin-binding subunit MtrA is not homologous to any known B12-binding proteins and is proposed as the motor of the sodium-ion pump. Here, we present crystal structures of the soluble domain of the membrane-associated MtrA from Methanocaldococcus jannaschii and the cytoplasmic MtrA homologue/cobalamin complex from Methanothermus fervidus. The MtrA fold corresponds to the Rossmann-type α/β fold, which is also found in many cobalamin-containing proteins. Surprisingly, the cobalamin-binding site of MtrA differed greatly from all the other cobalamin-binding sites. Nevertheless, the hydrogen-bond linkage at the lower axial-ligand site of cobalt was equivalently constructed to that found in other methyltransferases and mutases. A distinct polypeptide segment fixed through the hydrogen-bond linkage in the relaxed Co(III) state might be involved in propagating the energy released upon corrinoid demethylation to the sodium-translocation site by a conformational change.