Human malignant melanoma exhibits imbalances in redox status, leading to activation of many redox-sensitive signaling pathways. APE/Ref-1 is a multifunctional protein that serves as a redox chaperone that regulates many nuclear transcription factors and is an important mechanism in cancer cell survival of oxidative stress. Previous studies showed that APE/Ref-1 is a potential druggable target for melanoma therapy. In this study, we synthesized a novel APE/Ref-1 inhibitor, bis-cinnamoyl-1,12-dodecamethylenediamine (2). In a xenograft mouse model, compound 2 treatment (5 mg/kg) significantly inhibited tumor growth compared to the control group, with no significant systemic toxicity observed. We further synthesized compound 2 analogs to determine the structure-activity relationship based on their anti-melanoma activities. Among those, 4-hydroxyphenyl derivative (11) exhibited potent anti-melanoma activities and improved water solubility compared to its parental compound 2. The IC50 of compound 11 was found to be less than 0.1 μM. Compared to other known APE/Ref-1 inhibitors, compound 11 exhibited increased potency in inhibiting melanoma proliferation. As determined by luciferase reporter analyses, compound 2 was shown to effectively inhibit H2O2-activated AP-1 transcription activities. Targeting APE/Ref-1-mediated signaling using pharmaceutical inhibitors is a novel and effective strategy for melanoma treatment with potentially high impact.