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. Polytheonamides are giant peptide toxins produced by the uncultivated sponge bacterium Entotheonella factor. The biosynthesis of polytheonamides involves up to 50 post-translational modifications. Now, heterologous expression in Escherichia coli and Rhizobium hosts have shown that a minimalistic, iterative enzyme set introduces this exceptional molecular complexity via epimerizations, C-/N-methylations, hydroxylations, dehydration and proteolytic maturation.