Two new cyclic depsipeptides wewakamide A (1) and guineamide G (2) have been isolated from the marine cyanobacterium Lyngbya semiplena and Lyngbya majuscula, respectively, collected from Papua New Guinea. The amino and hydroxy acid partial structures of wewakamide A and guineamide G were elucidated through extensive spectroscopic techniques, including HR-FABMS, 1D (1)H and (13)C NMR, as well as 2D COSY, HSQC, HSQCTOCSY, and HMBC spectra. The sequence of the residues of wewakamide A was determined through a combination of ESI-MS/MS, HMBC, and ROESY. Wewakamide A possesses a β-amino acid, 3-amino-2-methylbutanoic acid (Maba) residue, which has only been previously identified in two natural products, guineamide B (3) and dolastatin D (4). Although both new compounds (1,2) showed potent brine shrimp toxicity, only guineamide G displayed significant cytotoxicity to a mouse neuroblastoma cell line with LC(50) values of 2.7 micrometer.