Three new anabaenopeptin-like peptides, named paltolides A-C, were isolated from a deep-water specimen of the marine sponge Theonella swinhoei from Palau. Paltolides belong to a rare subgroup of sponge-derived anabaenopeptins that have in common a C-terminal tryptophan residue linked to the epsilon-amine of a lysine bearing a d configuration. The structures of paltolides A-C were determined by NMR and tandem MS techniques. Paltolide A is the first anabaenopeptin structure where a non-N-methylated amino acid precedes the C-terminal residue.