The methylation of peptide backbone amides is a hallmark of bioactive natural products, and it also greatly modifies the pharmacology of synthetic peptides. Usually, bioactive N-methylated peptides are cyclic. However, there is very limited knowledge about how post-translational enzymes can be applied to the synthesis of designed N-methylated peptides or peptide libraries. Here, driven by the established ability of some RiPP enzymes to process diverse substrates, we sought to define catalysts for the in vivo and in vitro macrocyclization of backbone-methylated peptides. We developed efficient methods in which short, synthetic N-methylated peptides could be modified using side chain and mainchain macrocyclases, PsnB and PCY1 from plesiocin and orbitide biosynthetic pathways, respectively. Most significantly, a strategy for PsnB cyclase was designed enabling simple in vitro methods compatible with solid-phase peptide synthesis. We show that cyanobactin N-terminal protease PatA is a broadly useful catalyst that is also compatible with N-methylation chemistry, but that cyanobactin macrocyclase PatG is strongly biased against N-methylated substrates. Finally, we sought to marry these macrocyclase tools with an enzyme that N-methylates its core peptide: OphMA from the omphalotin pathway. However, instead, we reveal some limitations of OphMA and demonstrate that it unexpectedly and extensively modified the enzyme itself in vivo. Together, these results demonstrate proof-of-concept for enzymatic synthesis of N-methylated peptide macrocycles.