Peptide antibiotics represent a class of conformationally constrained natural products of growing pharmaceutical interest. Plantazolicin (PZN) is a linear, polyheterocyclic natural product with highly selective and potent activity against the anthrax-causing bacterium, Bacillus anthracis. The bioactivity of PZN is contingent on dimethylation of its N-terminal Arg residue by an S-adenosylmethionine-dependent methyltransferase. Here, we explore the substrate tolerances of two homologous PZN methyltransferases by carrying out kinetic analyses of the enzymes against a synthetic panel of truncated PZN analogs containing the N-terminal Arg residue. X-ray cocrystal structures of the PZN methyltransferases with each of these heterocycle-containing substrates provide a rationale for understanding the strict substrate specificity of these enzymes. Kinetic studies of structure-guided, site-specific variants allowed for the assignment of residues governing catalysis and substrate scope. Microbiological testing further revealed that upon dimethylation of the N-terminal Arg, a pentaheterocyclized PZN analog retained potent anti-B. anthracis activity, nearly equal to that of full-length PZN. These studies may be useful in the biosynthetic engineering of natural product analogs with different bioactivity profiles, as demonstrated by our identification of a truncated plantazolicin derivative that is active against methicillin-resistant Staphylococcus aureus (MRSA).