Background: Drug resistance in Plasmodium falciparum poses a major threat to malaria control. Combination antimalarial therapy including artemisinins has been advocated recently to improve efficacy and limit the spread of resistance, but artemisinins are expensive and relatively untested in highly endemic areas. We compared artemisinin-based and other combination therapies in four districts in Uganda with varying transmission intensity. Methods and Findings: We enrolled 2,160 patients aged 6 mo or greater with uncomplicated falciparum malaria. Patients were randomized to receive chloroquine (CQ) + sulfadoxine-pyrimethamine (SP); amodiaquine (AQ) + SP; or AQ + artesunate (AS). Primary endpoints were the 28-d risks of parasitological failure either unadjusted or adjusted by genotyping to distinguish recrudescence from new infections. A total of 2,081 patients completed follow-up, of which 1,749 (84%) were under the age of 5 y. The risk of recrudescence after treatment with CQ + SP was high, ranging from 22% to 46% at the four sites. This risk was significantly lower (p < 0.01) after AQ + SP or AQ + AS (7%-18% and 4%-12%, respectively). Compared to AQ + SP, AQ + AS was associated with a lower risk of recrudescence but a higher risk of new infection. The overall risk of repeat therapy due to any recurrent infection (recrudescence or new infection) was similar at two sites and significantly higher for AQ + AS at the two highest transmission sites (risk differences = 15% and 16%, p < 0.003). Conclusion: AQ + AS was the most efficacious regimen for preventing recrudescence, but this benefit was outweighed by an increased risk of new infection. Considering all recurrent infections, the efficacy of AQ + SP was at least as efficacious at all sites and superior to AQ + AS at the highest transmission sites. The high endemicity of malaria in Africa may impact on the efficacy of artemisinin-based combination therapy.