A novel compound, named plumisclerin A (1), was isolated from samples of the soft coral Plumigorgia terminosclera collected at Mayotte Island. The compound possesses the novel plumisclerane carbon skeleton, including a tricyclo[4,3,1,0(1,5)]decane ring. Its structure and relative stereochemistry were elucidated by extensive spectroscopic analysis, including HREIMS, COSY, HSQC, HMBC, TOCSY, and NOESY experiments. In addition, the novel compound displayed in vitro cytotoxicity against selected cancer cell lines.