Two new 15-hydroxycembranoid diterpenes, 2β-hydroxy-7β,8α-epoxynephthenol (1) and 2β-hydroxy-11α,12β-epoxynephthenol (2), were isolated from extracts of the octocoral Nephthea columnaris along with a new natural cembrane, epoxynephthenol (3) and a known sterol, nephalsterol A (4). The structures of cembranes 1–3 were elucidated by spectroscopic methods and comparison of the spectroscopic data with those of related analogues. The cytotoxicity of metabolites 1–4 against a panel of tumor cells is also described.