A new sulfated cyclic depsipeptide, termed mutremdamide A, and six new highly N-methylated peptides, termed koshikamides C-H, were isolated from different deep-water specimens of Theonella swinhoei and Theonella cupola. Their structures were determined using extensive 2D NMR, ESI, or CDESI and QTOF-MS/MS experiments and absolute configurations established by quantum mechanical calculations, advanced Marfey's method, and chiral HPLC. Mutremdamide A displays a rare 2-amino-3-(2-hydroxyphenyl)propanoic acid and a new N(delta)-carbamoyl-beta-sulfated asparagine. Koshikamides C-E are linear undecapeptides, and koshikamides F-H are 17-residue depsipeptides containing a 10-residue macrolactone. Koshikamides F and G differ from B and H in part by the presence of the conjugated unit 2-(3-amino-5-oxopyrrolidin-2-ylidene)propanoic acid. Cyclic koshikamides F and H inhibited HIV-1 entry at low micromolar concentrations while their linear counterparts were inactive. The Theonella collections studied here are distinguished by co-occurrence of mutremdamide A, koshikamides, and theonellamides, the combination of which appears to define a new Theonella chemotype that can be found in deeper waters.