Propolis is a resin that is gathered by bees from exudates produced by various plants. Its exact chemical composition depends on the plants available near the hive. Bees use propolis to coat the surfaces of the hive, where it acts as an anti-infective. Regardless of the chemical composition of propolis, it is always anti-protozoal, probably because protozoan parasites, particularly Lotmarium passim, are widespread in bee populations. The protozoa Trypanosoma brucei and T. congolense cause disease in humans and/or animals. The existing drugs for treating these diseases are old and resistance is an increasingly severe problem. The many types of propolis present a rich source of anti-trypanosomal compounds—from a material gathered by bees in an environmentally friendly way. In the current work, red Nigerian propolis from Rivers State, Nigeria was tested against T. brucei and T. congolense and found to be highly active (EC50 1.66 and 4.00 µg/mL, respectively). Four isoflavonoids, vestitol, neovestitol, 7-methylvestitol and medicarpin, were isolated from the propolis. The isolated compounds were also tested against T. brucei and T. congolense, and vestitol displayed the highest activity at 3.86 and 4.36 µg/mL, respectively. Activities against drug-resistant forms of T. brucei and T. congolense were similar to those against wild type.