Uncultivated bacteria represent a massive resource of new enzymes and bioactive metabolites, but such bacteria remain functionally enigmatic. Polytheonamides are potent peptide cytotoxins produced by uncultivated bacteria that exist as symbionts in a marine sponge. Outside glycobiology, polytheonamides represent the most heavily post-translationally modified biomolecules that are derived from amino acids. The biosynthesis of polytheonamides involves up to 50 site-specific modifications to create a membrane-spanning β-helical structure. Here, we provide functional evidence that only seven enzymes are necessary for this process. They iteratively catalyse epimerization, methylation and hydroxylation of diverse amino acids. To reconstitute C-methylation, we employed the rarely used heterologous host Rhizobium leguminosarum to invoke the activities of two cobalamin-dependent C-methyltransferases. We observed 44 of the modifications to systematically unravel the biosynthesis of one of the most densely modified and metabolically obscure ribosome-derived molecules found in nature.