Nine new linear lipopeptides, microcolins E-M (<b>1</b>-<b>9</b>), together with four known related compounds, microcolins A-D (<b>10</b>-<b>13</b>), were isolated from the marine cyanobacterium <i>Moorea producens</i> using bioassay-guided and LC-MS/MS molecular networking approaches. Catalytic hydrogenation of microcolins A-D (<b>10</b>-<b>13</b>) yielded two known compounds, 3,4-dihydromicrocolins A and B (<b>14</b>, <b>15</b>), and two new derivatives, 3,4-dihydromicrocolins C and D (<b>16</b>, <b>17</b>), 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 (<i>N</i>-Me-homoisoleucine), in compounds <b>1</b>-<b>3</b> and <b>8</b>, respectively, are rare residues in naturally occurring peptides. These metabolites showed significant cytotoxic activity against H-460 human lung cancer cells with IC<sub>50</sub> 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.