The marine environment is a rich source of metabolites with potential therapeutic properties and applications for humans. Here we describe the first isolation, solid-phase total synthesis, and full structural assignment of a new class of cyclodepsipeptides from the Madagascan sponge Ecionemia acervus that shows in vitro cytotoxic activities at submicromolar concentrations. Seven structures belonging to a new family of compounds, given the general name stellatolides, were characterized. The sequence and stereochemistry of all the amino acids in these molecules were established by a combination of spectroscopic analysis, chemical degradation, and derivatization studies. Furthermore, the complete structure of stellatolide A was confirmed by an efficient solid-phase method for the first total synthesis and the full structural assignment of this molecule, including the asymmetric synthesis of the unique β-hydroxy acid moiety (Z)-3-hydroxy-6,8-dimethylnon-4-enoic acid.