Protein glutamine methylation at GGQ sites of protein chain release factors plays a pivotal role in the termination of translation. We report here the crystal structure of the Escherichia coli HemK protein (N5)-glutamine methyltransferase (MTase) in a binary complex with the methyl-donor product S-adenosyl-L-homocysteine (AdoHcy). HemK contains two domains: a putative substrate binding domain at the N terminus consisting of a five helix bundle and a seven-stranded catalytic domain at the C terminus that harbors the binding site for AdoHcy. The two domains are linked by a beta-hairpin. Structure-guided sequence analysis of the HemK family revealed 11 invariant residues functioning in methyl-donor binding and catalysis of methyl transfer. The putative substrate-binding domains of HemK from E.coli and Thermotoga maritima are structurally similar, despite the fact that they share very little sequence similarity. When the two proteins are aligned structurally, the helical N-terminal domain is subject to approximately 10 degrees of hinge movement relative to the C-terminal domain. The apparent hinge mobility of the two domains may reflect functional importance during the reaction cycle. Comparative phylogenetic analysis of the hemK gene and its frequent neighbor gene, prfA, which encodes a major substrate, provides evidence for several examples of lateral gene transfer.