Despite the advances in cancer therapies in the past century, malignant melanoma continues to present a significant clinical challenge due to lack of chemotherapeutic response. Systemic therapy with immunostimulatory agents such as interferon and interleukin-2 (IL-2) has shown some promise, though each is associated with significant side effects. Over the past 50 years, oncolytic Newcastle disease virus (NDV) has emerged as an alternative candidate for cancer therapy. The establishment of reverse-genetics systems for the virus has allowed us to further manipulate the virus to enhance its oncolytic activity. Introduction of immunomodulatory molecules, especially IL-2, into the NDV genome was shown to enhance the oncolytic potential of the virus in a murine syngeneic colon carcinoma model. We hypothesize that a recombinant NDV expressing IL-2 would be an effective agent for therapy of malignant melanoma. We show that recombinant NDV possesses a strong cytolytic activity against multiple melanoma cell lines, and is effective in clearing established syngeneic melanoma tumors in mice. Moreover, introduction of murine IL-2 into NDV significantly enhanced its activity against syngeneic melanomas, resulting in increased overall animal survival and generation of antitumor immunity. These findings warrant further investigations of IL-2-expressing NDV as an antimelanoma agent in humans.