A screening of Sudanese medicinal plants for antiprotozoal activities revealed that the chloroform and water fractions of the ethanolic root extract of Haplophyllum tuberculatum exhibited appreciable bioactivity against Leishmania donovani. The antileishmanial activity was tracked by HPLC-based activity profiling, and eight compounds were isolated from the chloroform fraction. These included lignans tetrahydrofuroguaiacin B (1), nectandrin B (2), furoguaiaoxidin (7), and 3,3′-dimethoxy-4,4′-dihydroxylignan-9-ol (10), and four cinnamoylphenethyl amides, namely dihydro-feruloyltyramine (5), (E)-N-feruloyltyramine (6), N,N′-diferuloylputrescine (8), and 7′-ethoxy-feruloyltyramine (9). The water fraction yielded steroid saponins 11–13. Compounds 1, 2, and 5–13 are reported for the first time from Haplophyllum species and the family Rutaceae. The antiprotozoal activity of the compounds plus two stereoisomeric tetrahydrofuran lignans—fragransin B2 (3) and fragransin B1 (4)—was determined against Leishmania donovani amastigotes, Plasmodium falciparum, and Trypanosoma brucei rhodesiense bloodstream forms, along with their cytotoxicity to rat myoblast L6 cells. Nectandrin B (2) exhibited the highest activity against L. donovani (IC50 4.5 µM) and the highest selectivity index (25.5).