Further chemical study of the crude extract of the soft coral Heteroxenia fuscescens (Fam., Xeniidea), led to isolation of two new sterols, Heterofuscesterols A (1) and B (2), a sterol isolated for the first time from natural sources, 3β,5α,6β-trihydroxyandrosta-17-one (3), along with one new hydroperoxy sesquiterpene, Heterofusceterpene A (4), and one known ceramide (5). Their structures were elucidated by comprehensive spectroscopic analyses, including NMR and HRESIMS, and by comparison with previous data for related compounds in the literature. The cytotoxic activities of the isolated compounds were assessed using MTT colorimetric assay against MCF-7 and OVK-18 cancer cell lines.