Two new asterosaponins, lethasteriosides A (1) and B (2), were isolated along with previously known thornasteroside A (3), anasteroside A (4), and luidiaquinoside (5) from the ethanolic extract of the Far Eastern starfish Lethasterias fusca. The structures of the new compounds were elucidated by extensive NMR and ESIMS techniques, and chemical transformations. Compounds 1 and 3-5 did not show any apparent cytotoxicity against cancer cell lines T-47D, RPMI-7951, and HCT-116, but glycoside 1, at concentration of 20 microM, demonstrated considerable inhibition of the T-47D (97%), RPMI-795I (90%) and HCT-116 (90%) cell colony formations in a soft agar clonogenic assay.