Two new pregnane-type steroidal glycosides, pregna-5,20-dien-3-O-alpha-fucopyranoside (1) and pregna-20-en-3-O-alpha-fucopyranoiside (2), along with two known pregnane derivatives, were isolated from the soft coral Cladiella krempfi. Their structures were determined by spectroscopic data analysis.