Resistance to chloroquine (CQ) requires its replacement as first-line therapy for uncomplicated malaria in much of Africa. Combination therapy may improve efficacy and delay the selection of resistant malaria parasites. Combinations of sulfadoxine-pyrimethamine (SP) with 4-aminoquinolines offer affordable and available alternatives to CQ. We conducted a randomized, single-blinded trial to compare the efficacy of SP monotherapy with combinations of SP and either CQ or amodiaquine (AQ) for the treatment of uncomplicated falciparum malaria in patients over 6 months of age in Kampala, Uganda. Of the 448 patients enrolled, 428 (95%) completed follow-up. Clinical treatment failure after 14 days occurred in 21/140 (15.0%, 95% CI 9.5-22.0%) SP-treated, 11/152 (7.2%, 95% CI 3.7-12.6%) SP/CQ-treated, and 0/136 (0%, 95% CI 0-2.7%) SP/AQ-treated patients. Combination therapies were safe and offered superior efficacy to SP monotherapy. SP/AQ was the most efficacious. This low-cost combination regimen may provide an optimal alternative to CQ for the treatment of uncomplicated malaria in Uganda.