Based on our previous finding that certain cembranoid diterpenes possess selective toxicity against protozoan pathogens of tropical diseases such as Trypanosoma and Plasmodium, we have subjected a series of 34 cembranes isolated from soft corals living in the Vietnamese sea to an in vitro screening for anti-protozoal activity against Trypanosoma brucei rhodesiense (Tbr), T. cruzi (Tc), Leishmania donovani (Ld), and Plasmodium falciparum (Pf). Twelve of the tested compounds displayed significant activity against at least one of the parasites. Specifically, 7S,8S-epoxy-1,3,11-cembratriene-16-oic methyl ester (1), (1R,4R,2E,7E,11E)-cembra-2,7,11-trien-4-ol (2), crassumol D (12), crassumol E (13), and (1S,2E,4S,6E,8S,11S)-2,6,12(20)-cembrantriene-4,8,11-triol (16) from Lobophytum crassum, L. laevigatum, and Sinularia maxima showed the highest level of inhibitory activity against T. b. rhodesiense, with IC50 values of about 1 µM or less. Lobocrasol A (6) and lobocrasol C (8) from L. crassum and L. laevigatum exhibited particularly significant inhibitory effects on L. donovani with IC50 values < 0.2 µM. The best antiplasmodial effect was exerted by laevigatol A (10), with an IC50 value of about 3.0 µM. The cytotoxicity of the active compounds on L6 rat skeletal myoblast cell was also assessed and found to be insignificant in all cases. This is the first report on anti-protozoal activity of these compounds, and points out the potential of the soft corals in discovery of new anti-protozoal lead compounds.