An investigation of the polar extracts from two starfish, Luidia quinaria and Psilaster cassiope, led to the isolation of five sulfated "asterosaponins". Two of them, named luidiaquinoside (1) and psilasteroside (2), are new compounds. Luidiaquinoside (1) contains a novel pentasaccharide chain composed of d-glucose, d-quinovose, and d-fucose, with the d-glucose unit being the branching point. Psilasteroside (2) contains a hexasaccharide chain in which an arabinose residue is detectable in the furanose form. Both of these compounds possess a Delta(9(11)),3beta,6alpha-dihydroxysteroidal nucleus with a 20-hydroxy, 23-oxo functionality. The structures of the new asterosaponins were elucidated by a combination of NMR techniques including (1)H-(1)H (COSY, TOCSY, and ROESY) and (1)H-(13)C (HMQC and HMBC) spectroscopy, ESIMS and HRFABMS spectrometry, and GC analyses. The new asterosaponins show marginal in vitro cytotoxicity against RBL-2H3 (rat basophilic leukemia) cell lines.