Cobalamin-dependent radical S-adenosylmethionine (rSAM) methyltransferases catalyze chemically challenging methylation reactions on diverse natural products at unactivated carbon centers. In vivo reconstitution and biosynthetic studies of natural product gene clusters encoding these enzymes are often severely limited by ineffective heterologous expression hosts, including the otherwise versatile Escherichia coli. In this chapter, we describe the use of rhizobia bacteria as effective expression hosts for cobalamin-dependent rSAM C-methyltransferases. We chose the natural product pathway encoding the heavily modified cytotoxic peptides, the polytheonamides, as our model pathway due to the presence of two methyltransferases responsible for a total of 17 C-methylations. Detailed protocols are given for vector construction, transformation, and heterologous expression in Rhizobium leguminosarum bv. viciae 3841. Additional methods pertaining to analytical separation and mass spectrometric analysis of modified peptides are also entailed. As genomics continues to uncover new enzymes and pathways from unknown and uncultivated microbes, use of metabolically distinct heterologous expression hosts like rhizobia will be a necessary tool to unravel the catalytic and metabolic diversity of marine microbial life.