Four new diterpenoids, cespitulactones A-B (1-2), C4B1 (7) and E3A (8), were isolated from the soft coral Cespitularia taeniata collected in Taiwan, at a depth of 25 m, together with five known compounds, cespitularin F (3), 6-O-acetylcespitularin F (4), cespitularin D (5), flaccidoxide-13-acetate (6) and florlide A (9). Compound 1 possesses a novel structure with a bond cleavage between C-10 and C-11, and having a 14-membered lactone ring junction between C-10 and C-12. Compounds 2 and 8 have the verticillane skeleton, and compound 9 possesses the cespitularane skeleton. Their structures were elucidated on the basis of extensive spectroscopic analysis and chemical derivatization. The isolated compounds were also evaluated for cytotoxicity toward human cancer cell lines. Compound 1 exhibited significant cytotoxicity against human cervical epitheloid carcinoma (HeLa) and colon adenocarcinoma (DLD-1) cancer cells with IC50 of 3.69 and 9.98 £gg/mL, respectively. Flaccidoxide-13-acetate (6) showed mild activity against human medulloblastoma (Daoy) and colon (WiDr) cancer cells at 16.9 and 13.8 £gg/mL, respectively.