Two new triterpene glycosides, namely holothurin A3 (1) and A4 (2) were isolated from the methanol extract of the sea cucumber, Holothuria scabra, with their structures elucidated from the spectroscopic evidence (1D NMR, 2D NMR, ESI-MS and HRESI-MS). Compounds 1 and 2 were found to be strongly cytotoxic to both cancer cell lines, KB and Hep-G2, with 50% inhibitory concentrations (IC50) of 0.87 and 0.32 microg/mL (for compound 1) and of 1.12 and 0.57 microg/mL (for compound 2), respectively.