The posttranslational modification of C-terminal CAAX motifs in proteins such as Ras, most Rho GTPases, and G protein γ subunits, plays an essential role in determining their subcellular localization and correct biological function. An integral membrane methyltransferase, isoprenylcysteine carboxyl methyltransferase (ICMT), catalyzes the final step of CAAX processing after prenylation of the cysteine residue and endoproteolysis of the -AAX motif. We have determined the crystal structure of a prokaryotic ICMT ortholog, revealing a markedly different architecture from conventional methyltransferases that utilize S-adenosyl-L-methionine (SAM) as a cofactor. ICMT comprises a core of five transmembrane α helices and a cofactor-binding pocket enclosed within a highly conserved C-terminal catalytic subdomain. A tunnel linking the reactive methyl group of SAM to the inner membrane provides access for the prenyl lipid substrate. This study explains how an integral membrane methyltransferase achieves recognition of both a hydrophilic cofactor and a lipophilic prenyl group attached to a polar protein substrate.