Lanthipeptides are ribosomally derived peptide secondary metabolites that undergo extensive posttranslational modification. Prochlorosins are a group of lanthipeptides produced by certain strains of the ubiquitous marine picocyanobacteria Prochlorococcus and Synechococcus Unlike other lanthipeptide-producing bacteria, picocyanobacteria use an unprecedented mechanism of substrate promiscuity for the production of numerous and diverse lanthipeptides using a single lanthionine synthetase. Through a cross-scale analysis of prochlorosin biosynthesis genes-from genomes to oceanic populations-we show that marine picocyanobacteria have the collective capacity to encode thousands of different cyclic peptides, few of which would display similar ring topologies. To understand how this extensive structural diversity arises, we used deep sequencing of wild populations to reveal genetic variation patterns in prochlorosin genes. We present evidence that structural variability among prochlorosins is the result of a diversifying selection process that favors large, rather than small, sequence changes in the precursor peptide genes. This mode of molecular evolution disregards any conservation of the ancestral structure and enables the emergence of extensively different cyclic peptides through short mutational paths based on indels. Contrary to its fast-evolving peptide substrates, the prochlorosin lanthionine synthetase evolves under a strong purifying selection, indicating that the diversification of prochlorosins is not constrained by commensurate changes in the biosynthetic enzyme. This evolutionary interplay between the prochlorosin peptide substrates and the lanthionine synthetase suggests that structure diversification, rather than structure refinement, is the driving force behind the creation of new prochlorosin structures and represents an intriguing mechanism by which natural product diversity arises.