Ten new prostaglandin derivatives (PGs), sarcoehrendins A-J (1-10), together with five known analogues (11-15) were isolated from the soft coral Sarcophyton ehrenbergi. Compounds 4-8 represented the first examples of PGs featuring an 18-ketone group. The structures including the absolute configurations were elucidated on the basis of spectroscopic analysis and chemical evidence. All of the isolates and six synthetic analogues (3a, 3b, 4a, and 11a-11c) were screened for inhibitory activity against phosphodiesterase-4 (PDE4), which is a drug target for the treatment of asthma and chronic obstructive pulmonary disease. Compounds 2, 10, 11a, 11b, and 13-15 exhibited inhibition with IC50 values less than 10 μM, and compound 15 (IC50 = 1.4 μM) showed comparable activity to the positive control rolipram (IC50 = 0.60 μM). The active natural PGs (2, 10, and 13-15) represent the first examples of PDE4 inhibitors without an aromatic moiety, and a preliminary structure-activity relationship is also proposed.