The polytheonamides are among the most complex and biosynthetically distinctive natural products known to date. These potent peptide cytotoxins are derived from a ribosomal precursor processed by 49 mostly non-canonical posttranslational modifications. As the producer is a 'microbial dark matter' bacterium only distantly related to any cultivated organism, >70-step chemical syntheses have been developed to access these unique compounds. Here, we mined prokaryotic diversity to establish a synthetic platform based on the new host Microvirgula aerodenitrificans that produces hypermodified peptides within two days. Using this system, we generated the aeronamides, new polytheonamide-type compounds with near-picomolar cytotoxicity. Aeronamides, as well as the polygeonamides produced from deep-rock biosphere DNA, contain the highest numbers of D-amino acids in known biomolecules. With increasing bacterial genomes being sequenced, similar host mining strategies might become feasible to access further elusive natural products from uncultivated life.