Super-resistant Plasmodium falciparum threatens the effectiveness of sulfadoxine-pyrimethamine in intermittent preventive treatment for malaria during pregnancy. It is characterized by the A581G Pfdhps mutation on a background of the double-mutant Pfdhps and the triple-mutant Pfdhfr. Using samples collected during 2004-2008, we investigated the evolutionary origin of the A581G mutation by characterizing microsatellite diversity flanking Pfdhps triple-mutant (437G+540E+581G) alleles from 3 locations in eastern Africa and comparing it with double-mutant (437G+540E) alleles from the same area. In Ethiopia, both alleles derived from 1 lineage that was distinct from those in Uganda and Tanzania. Uganda and Tanzania triple mutants derived from the previously characterized southeastern Africa double-mutant lineage. The A581G mutation has occurred multiple times on local Pfdhps double-mutant backgrounds; however, a novel microsatellite allele incorporated into the Tanzania lineage since 2004 illustrates the local expansion of emergent triple-mutant lineages.