Aeruginosins represent a group of peptide metabolites isolated from various cyanobacterial genera and from marine sponges that potently inhibit different types of serine proteases. Members of this family are characterized by the presence of a 2-carboxy-6-hydroxyoctahydroindole (Choi) moiety. We have identified and fully sequenced a NRPS gene cluster in the genome of the cyanobacterium Planktothrix agardhii CYA126/8. Insertional mutagenesis of a NRPS component led to the discovery and structural elucidation of two new glycopeptides that were designated aeruginoside 126A and aeruginoside 126B. One variant of the aglycone contains a 1-amino-2-(N-amidino-Δ3-pyrrolinyl)ethyl moiety at the C-terminus, the other bears an agmatine residue. In silico analyses of the aeruginoside biosynthetic genes aerA-aerI as well as additional mutagenesis and feeding studies allowed the prediction of enzymatic steps leading to the formation of aeruginosides and the unusual Choi moiety.