Accumulation of mutations in dihydrofolate reductase (dhfr) and dihydropteroate synthetase (dhps) is strongly associated with sulfadoxine-pyrimethamine (SP) treatment failure. Routine surveillance for these resistance markers was conducted annually at 26 sentinel sites in Maputo Province, Mozambique, before and after the phased deployment of artesunate plus SP (AS-SP), with 15,758 children sampled between 2004 and 2008. Mean asexual parasite prevalence, polymerase chain reaction (PCR) corrected, decreased from 44.2% in 2004 to 3.8% in 2008 (P < 0.0001). Among the 2,012 PCR-confirmed falciparum samples, the dhfr triple mutation remained close to fixation, whereas both dhps double and dhfr/dhps "quintuple" mutations increased from 11.0% in 2004, to 75.0% by 2008 (P < 0.0001). Adding artesunate to SP did not retard the spread of SP-resistant parasites. The high "quintuple" mutation prevalence suggests a limited useful therapeutic lifespan of AS-SP for treating uncomplicated malaria, and may curb efficacy of SP-monotherapy for intermittent preventive treatment in Mozambique.