Plantazolicin (PZN), a polyheterocyclic, N-alpha, N-alpha-dimethylarginine-containing antibiotic, harbors remarkably specific bactericidal activity toward strains of Bacillus anthracis, the causative agent of anthrax. Previous studies demonstrated that genetic deletion of the S-adenosyl-L-methionine-dependent methyltransferase from the PZN biosynthetic gene cluster results in the formation of desmethylPZN, which is devoid of antibiotic activity. Here we describe the in vitro reconstitution, mutational analysis, and X-ray crystallographic structure of the PZN methyltransferase. Unlike all other known small molecule methyltransferases, which act upon diverse substrates in vitro, the PZN methyltransferase is uncharacteristically limited in substrate scope and functions only on desmethylPZN and close derivatives. The crystal structures of two related PZN methyltransferases, solved to 1.75 angstrom (Bacillus amyloliquefaciens) and 2.0 angstrom (Bacillus pumilus), reveal a deep, narrow cavity, putatively functioning as the binding site for desmethylPZN. The narrowness of this cavity provides a framework for understanding the molecular basis of the extreme substrate selectivity. Analysis of a panel of point mutations to the methyltransferase from B. amyloliquefaciens allowed the identification of residues of structural and catalytic importance. These findings further our understanding of one set of orthologous enzymes involved in thiazole/oxazole-modified microcin biosynthesis, a rapidly growing sector of natural products research.