Background: Cutaneous Leishmania major has affected many travelers including military personnel in Iraq and Afghanistan. Optimal treatment for this localized infection has not been defined, but interestingly the parasite is thermosensitive. Methodology/Principal Findings: Participants with parasitologically confirmed L. major infection were randomized to receive intravenous sodium stibogluconate (SSG) 20mg/kg/day for ten doses or localized ThermoMed (TM) device heat treatment (applied at 50°C for 30 seconds) in one session. Those with facial lesions, infection with other species of Leishmania, or more than 20 lesions were excluded. Primary outcome was complete re-epithelialization or visual healing at two months without relapse over 12 months. Fifty-four/56 enrolled participants received intervention, 27 SSG and 27 TM. In an intent to treat analysis the per subject efficacy at two months with 12 months follow-up was 54% SSG and 48% TM (p = 0.78), and the per lesion efficacy was 59% SSG and 73% TM (p = 0.053). Reversible abdominal pain/pancreatitis, arthralgias, myalgias, headache, fatigue, mild cytopenias, and elevated transaminases were more commonly present in the SSG treated participants, whereas blistering, oozing, and erythema were more common in the TM arm. Conclusions/Significance: Skin lesions due to L. major treated with heat delivered by the ThermoMed device healed at a similar rate and with less associated systemic toxicity than lesions treated with intravenous SSG. Clinical Trial Registration: ClinicalTrials.gov NCT 00884377.