We present here a nonviral immunogene therapy trial for canine malignant melanoma, an aggressive disease displaying significant clinical and histopathological overlapping with human melanoma. As a surgery adjuvant approach, it comprised the co-injection of lipoplexes bearing herpes simplex virus thymidine kinase and canine interferon-β genes at the time of surgery, combined with the periodic administration of a subcutaneous genetic vaccine composed of tumor extracts and lipoplexes carrying the genes of human interleukin-2 and human granulocyte-macrophage colony-stimulating factor. Following complete surgery (CS), the combined treatment (CT) significantly raised the portion of local disease-free canine patients from 11% to 83% and distant metastases-free (M0) from 44% to 89%, as compared with surgery-only-treated controls (ST). Even after partial surgery (PS), CT better controlled the systemic disease (M0: 82%) than ST (M0: 48%). Moreover, compared with ST, CT caused a significant 7-fold (CS) and 4-fold (PS) rise of overall survival, and >17-fold (CS) and >13-fold (PS) rise of metastasis-free survival. The dramatic increase of PS metastasis-free survival (>1321 days) and CS recurrence- and metastasis-free survival (both >2251 days) demonstrated that CT was shifting a rapidly lethal disease into a chronic one. In conclusion, this surgery adjuvant CT was able of significantly delaying or preventing postsurgical recurrence and distant metastasis, increasing disease-free and overall survival, and maintaining the quality of life. The high number of canine patients involved in CT (301) and the extensive follow-up (>6 years) with minimal or absent toxicity warrant the long-term safety and efficacy of this treatment. This successful clinical outcome justifies attempting a similar scheme for human melanoma.