Phosphatase and tensin homolog (PTEN) loss is associated with genomic instability. APE1 is a key player in DNA base excision repair (BER) and an emerging drug target in cancer. We have developed small molecule inhibitors against APE1 repair nuclease activity. In the current study we explored a synthetic lethal relationship between PTEN and APE1 in melanoma. Clinicopathological significance of PTEN mRNA and APE1 mRNA expression was investigated in 191 human melanomas. Preclinically, PTEN-deficient BRAF-mutated (UACC62, HT144, and SKMel28), PTEN-proficient BRAF-wildtype (MeWo), and doxycycline-inducible PTEN-knockout BRAF-wildtype MeWo melanoma cells were DNA repair expression profiled and investigated for synthetic lethality using a panel of four prototypical APE1 inhibitors. In human tumours, low PTEN mRNA and high APE1 mRNA was significantly associated with reduced relapse free and overall survival. Pre-clinically, compared to PTEN-proficient cells, PTEN-deficient cells displayed impaired expression of genes involved in DNA double strand break (DSB) repair. Synthetic lethality in PTEN-deficient cells was evidenced by increased sensitivity, accumulation of DSBs and induction of apoptosis following treatment with APE1 inhibitors. We conclude that PTEN deficiency is not only a promising biomarker in melanoma, but can also be targeted by a synthetic lethality strategy using inhibitors of BER, such as those targeting APE1.