N-methylation of nucleic acids, proteins, and peptides is a chemical modification with significant impact on biological regulation. Despite the simplicity of the structural change, N-methylation can influence diverse functions including epigenetics, protein complex formation, and microtubule stability. While there are limited examples of N-methylation of the α-amino group of bacterial and eukaryotic proteins, there are no examples of catalysts that carry out post-translation methylation of backbone amides in proteins or peptides. Recent studies have identified enzymes that catalyze backbone N-methylation on a peptide substrate, a reaction with little biochemical precedent, in a family of ribosomally synthesized natural products produced in basidiomycetes. Here, we describe the crystal structures of Dendrothele bispora dbOphMA, a methyltransferase that catalyzes multiple N-methylations on the peptide backbone. We further carry out biochemical studies of this catalyst to determine the molecular details that promote this unusual chemical transformation. The structural and biochemical framework described here could facilitate biotechnological applications of catalysts for the rapid production of backbone N-methylated peptides.