Leptohelia flexibilis gen. nov. et sp. nov., the first stylasterid with a combined calcified and non-calcified skeleton, is described from seamounts and the slope off the islands of New Caledonia, in the southwestern Pacific. The new species is distinguished from all other species of the family Stylasteridae by having a non-calcified organic axis, internal to the basal portion of the calcified corallum. The internal axis is flexible and enclosed by a series of up to 10 calcified annuli, allowing passive lateral bending of the colony. Molecular phylogenetic analyses confirm that Leptohelia flexibilis is a stylasterid coral and reveal that the species is closely related to Leptohelia microstylus comb. nov., a southwestern Pacific stylasterid that lacks an internal axis.