The safety and the efficacy of amodiaquine (AQ) alone, AQ plus sulfadoxine-pyrimethamine (SP) (AQ plus SP), and artesunate (ART) plus SP (ART plus SP), three possible alternatives to chloroquine (CQ), were investigated in 379 Rwandan children 6–59 months old with uncomplicated Plasmodium falciparum malaria who visited one urban/peri-urban health center and two rural health centers. The three treatment regimens were well tolerated and no serious adverse effects were observed. Children treated with AQ plus SP had less clinical failures than those treated with ART plus SP (odds ratio [OR] = 0.25, 95% confidence interval [CI] = 0.06–0.81, P = 0.01) or AQ alone (OR = 0.33, 95% CI = 0.07–1.10, P = 0.08). Even after new infections were excluded, AQ plus SP was still significantly more efficacious than ART plus SP (P = 0.05). At day 14, the mean packed cell volume was significantly higher in the AQ plus SP group compared with the ART plus SP group (P = 0.02) and with the AQ alone group (P = 0.01). In Rwanda, AQ plus SP has been chosen to replace CQ as a first-line treatment. However, this is considered an interim measure and new combinations, possibly co-formulated, should be identified and tested.