Two new sulfated steroidal pentaglycosides (asterosaponins), novaeguinosides I (2) and II (3), along with the known regularoside B (1) were isolated from the starfish Culcita novaeguineae. Their structures were elucidated by extensive NMR techniques as well as chemical evidence. The new asterosaponins showed marginal in vitro cytotoxicity against two human tumor cell lines.