Six new sesquiterpenoids, paralemnolins J—O (1—6), along with one novel norsesquiterpenoid, paralemnolin P (7), have been isolated from the soft coral Paralemnalia thyrsoides . The structures of metabolites 1—7 were established on the basis of extensive NMR study and chemical methods. The structure of 5 was further confirmed by a single-crystal X-ray analysis. Cytotoxicity of these metabolites toward a limited panel of cancer cell lines also is described.