Trypanosomes cause disease in humans and livestock throughout sub-Saharan Africa. Although various species show evidence of clinical tolerance to trypanosomes, until now there has been no evidence of acquired immunity to natural infections. We discovered a distinct peak and decrease in age prevalence of T. brucei s.l. infection in wild African lions that is consistent with being driven by an exposure-dependent increase in cross-immunity following infections with the more genetically diverse species, T. congolense sensu latu. The causative agent of human sleeping sickness, T. brucei rhodesiense, disappears by 6 years of age apparently in response to cross-immunity from other trypanosomes, including the non-pathogenic subspecies, T. brucei brucei. These findings may suggest novel pathways for vaccinations against trypanosomiasis despite the notoriously complex antigenic surface proteins in these parasites.