Three new antiprotozoan compounds, gracilioethers A−C (1−3), have been isolated from the marine sponge Agelas gracilis. Their structures were elucidated on the basis of spectroscopic and chemical methods. Gracilioethers A−C showed antimalarial activity against Plasmodium falciparum with IC50 values of 0.5−10 μg/mL, whereas gracilioether B (2) also showed antileishmanial activity.