After 6 years of follow-up treating 364 canine melanoma patients, we present here results about the proof-of-concept, safety, and efficacy of a new surgery adjuvant combined gene therapy. The adjuvant treatment (AT) group was divided in three arms as follows: (i) complete surgery plus vaccine (CS-V), (ii) complete surgery plus combined treatment (CS-CT), and (iii) partial surgery plus combined treatment (PS-CT). Besides the genetic vaccines composed by tumor extracts and lipoplexes carrying human interleukin-2 and granulocyte-macrophage colony-stimulating factor genes, the patients were subjected to combined treatment received in the post-surgical bed injections of lipid-complexed thymidine kinase suicide gene plus ganciclovir and canine interferon-β gene plus bleomycin. As compared with surgery-only treated controls (So), CS-CT and CS-V treatments significantly increased the fraction of local disease-free (from 20 to 89 and 74%) and distant metastases-free patients (M0: from 45 to 87 and 84%). Although less effective than CS arms, PS-CT arm demonstrated a significantly improved control of metastatic disease (M0: 80%) compared with So (M0: 44%). In addition, AT produced a significant 9.3- (CS-CT), 6.5- (CS-V), and 5.4-fold (PS-CT) increase of overall survival as compared with their respective So controls. In general terms, the AT changed a lethal disease into a chronic disease where 70% of CS-CT, 51% of CS-V, and 14% of PS-CT patients died of melanoma unrelated causes. These surgery adjuvant treatments delayed or prevented post-surgical recurrence and distant metastasis, and improved disease-free and overall survival while maintaining quality of life. These successful outcomes encourage assaying a similar scheme for human melanoma.