Cytotoxicity-directed purification of a Symploca cf. hydnoides sample from Cetti Bay, Guam, afforded seven new cyclic depsipeptides, veraguamides A-G (1-7), together with the known compound dolastatin 16. The planar structures of 1-7 were elucidated using NMR and MS experiments, while enantioselective HPLC and Mosher's analysis of acid and base hydrolysates, respectively, were utilized to assign the absolute configurations of the stereocenters. Veraguamides A-G (1-7) are characterized by the presence of an invariant proline residue, multiple N-methylated amino acids, an α-hydroxy acid, and a C8-polyketide-derived β-hydroxy acid moiety with a characteristic terminus as either an alkynyl bromide, alkyne, or vinyl group. These compounds and a semisynthetic analogue (8) showed moderate to weak cytotoxic activity against HT29 colorectal adenocarcinoma and HeLa cervical carcinoma cell lines. Preliminary structure-activity relationship analysis identified several sensitive positions in the veraguamide scaffold that affect the cytotoxic activity of this compound class. Dolastatin 16 showed only weak cytotoxic activity on both cell lines tested. The complete stereostructure of dolastatin 16 was proposed for the first time through degradation followed by a combination of advanced Marfey's analysis and modified Mosher's analysis using phenylglycine methyl ester as a chiral anisotropic reagent.