Nine new linear lipopeptides, microcolins E-M (1-9), together with four known related compounds, microcolins A-D (10-13), were isolated from the marine cyanobacterium Moorea producens using bioassay-guided and LC-MS/MS molecular networking approaches. Catalytic hydrogenation of microcolins A-D (10-13) yielded two known compounds, 3,4-dihydromicrocolins A and B (14, 15), and two new derivatives, 3,4-dihydromicrocolins C and D (16, 17), respectively. The structures of these new compounds were determined by a combination of spectroscopic and advanced Marfey's analysis. Structurally unusual amino acid units, 4-methyl-2-(methylamino)pent-3-enoic (Mpe) acid and 2-amino-4-methylhexanoic acid (N-Me-homoisoleucine), in compounds 1-3 and 8, respectively, are rare residues in naturally occurring peptides. These metabolites showed significant cytotoxic activity against H-460 human lung cancer cells with IC50 values ranging from 6 nM to 5.0 μM. The variations in structure and attendant biological activities provided fresh insights concerning structure-activity relationships for the microcolin class of lipopeptides.