African trypanosomes are unusual among pathogenic protozoa in that they can undergo their complete morphological life cycle in the tsetse fly vector with mating as a non-obligatory part of this development. Trypanosoma brucei rhodesiense, which infects humans and livestock in East and Southern Africa, has classically been described as a host-range variant of the non-human infective Trypanosoma brucei that occurs as stable clonal lineages. We have examined T. b. rhodesiense populations from East (Uganda) and Southern (Malawi) Africa using a panel of microsatellite markers, incorporating both spatial and temporal analyses. Our data demonstrate that Ugandan T. b. rhodesiense existed as clonal populations, with a small number of highly related genotypes and substantial linkage disequilibrium between pairs of loci. However, these populations were not stable as the dominant genotypes changed and the genetic diversity also reduced over time. Thus these populations do not conform to one of the criteria for strict clonality, namely stability of predominant genotypes over time, and our results show that, in a period in the mid 1990s, the previously predominant genotypes were not detected but were replaced by a novel clonal population with limited genetic relationship to the original population present between 1970 and 1990. In contrast, the Malawi T. b. rhodesiense population demonstrated significantly greater diversity and evidence for frequent genetic exchange. Therefore, the population genetics of T. b. rhodesiense is more complex than previously described. This has important implications for the spread of the single copy T. b. rhodesiense gene that allows human infectivity, and therefore the epidemiology of the human disease, as well as suggesting that these parasites represent an important organism to study the influence of optional recombination upon population genetic dynamics.