Two novel pentacyclic guanidine alkaloids, celeromycalin 3 and fromiamycalin 4, have been isolated from the New Caledonian starfishes Celerina heffernani and Fromia monilis, respectively. Also found in Celerina heffernani are the known ptilomycalin A (1) and crambescidin 800 (2), which latter has been also isolated from Fromia monilis. The new compounds exhibited an high cytotoxic activity like the previous crambescidins. These complex pentacyclic guanidines are typical sponges metabolites and their occurence in starfishes is noteworthy. Fromia monilis also contained the less active component 5, made up from an hydroxyspermidine residue linked to a long chain ω-hydroxyacid.