Malignant melanoma is a cancer of the skin arising in the melanocytes. We present a mathematical model of melanoma invasion into healthy tissue with an immune response. We use this model as a framework with which to investigate primary tumor invasion and treatment by surgical excision. We observe that the presence of immune cells can destroy tumors, hold them to minimal expansion, or, through the production of angiogenic factors, induce tumorigenic expansion. We also find that the tumor-immune system dynamic is critically important in determining the likelihood and extent of tumor regrowth following resection. We find that small metastatic lesions distal to the primary tumor mass can be held to a minimal size via the immune interaction with the larger primary tumor. Numerical experiments further suggest that metastatic disease is optimally suppressed by immune activation when the primary tumor is moderately, rather than minimally, metastatic. Furthermore, satellite lesions can become aggressively tumorigenic upon removal of the primary tumor and its associated immune tissue. This can lead to recurrence where total cancer mass increases more quickly than in primary tumor invasion, representing a clinically more dangerous disease state. These results are in line with clinical case studies involving resection of a primary melanoma followed by recurrence in local metastases.