Background: Cutaneous leishmaniasis (CL) is treated with parenteral drugs for decades with decreasing rate cures. Miltefosine is an oral medication with anti-leishmania activity and may increase the cure rates and improve compliance. Methodology/Principal Findings: This study is a randomized, open-label, controlled clinical trial aimed to evaluate the efficacy and safety of miltefosine versus pentavalent antimony (Sbv) in the treatment of patients with CL caused by Leishmania braziliensis in Bahia, Brazil. A total of 90 patients were enrolled in the trial; 60 were assigned to receive miltefosine and 30 to receive Sbv. Six months after treatment, in the intention-to-treat analyses, the definitive cure rate was 53.3% in the Sbv group and 75% in the miltefosine group (difference of 21.7%, 95% CI 0.08% to 42.7%, p = 0.04). Miltefosine was more effective than Sbv in the age group of 13–65 years-old compared to 2–12 years-old group (78.9% versus 45% p = 0.02; 68.2% versus 70% p = 1.0, respectively). The incidence of adverse events was similar in the Sbv and miltefosine groups (76.7% vs. 78.3%). Vomiting (41.7%), nausea (40%), and abdominal pain (23.3%) were significantly more frequent in the miltefosine group while arthralgias (20.7%), mialgias (20.7%) and fever (23.3%) were significantly more frequent in the Sbv group. Conclusions: This study demonstrates that miltefosine therapy is more effective than standard Sbv and safe for the treatment of CL caused by Leishmania braziliensis in Bahia, Brazil.