Two new xenicanes, named protoxenicins A (1) and B (2), were isolated from an organic extract of the soft coral Protodendron repens, collected off the coast of Okuza (Tanzania), being the first chemical study of an organism belonging to this genus. Their planar structures were determined by 1D and 2D NMR and HRESIMS techniques, while the relative configurations were elucidated by comparison of their chemical shifts and coupling constants with the literature values of their congeners, as well as by ROESY experiments, chemical derivatization, and molecular mechanics calculations. This is the first report of a xenicin acylated with a long saturated fatty acid. Furthermore, the absolute configuration of the stereogenic centers of the cyclononane ring and at C-1 in 1 was determined by Mosher's method. Protoxenicin B (2) is present in solution as a mixture of two conformers in a 2:1 ratio deduced by 1H NMR. Both xenicanes display significant cytotoxic activity against a panel of different tumor cell lines.