Mental stress may have a negative impact on the immune state of cancer patients, in whom immunologic surveillance is essential for survival. This study investigated the immunological response of 19 patients with early-stage melanoma and a matched control group undergoing the Determination Stress Test before surgery. Cytokine and chemokine levels and lymphocyte subpopulations were measured at baseline and post-stress test time-points. Following the stress test lower levels of interleukin (IL)-6 were observed in the melanoma group compared with healthy volunteers (p = 0.044). IL-10 increased significantly in the control group 30 min after the stress test (p = 0.002) in comparison with the melanoma group (p = 0.407). CCL5/Rantes decreased significantly in the melanoma group, whereas CD16/CD56+ natural killer cells increased in both groups, with a sharp decrease below baseline after stress in the melanoma group (p = 0.001). This pilot study shows an altered immunological response to stressors in melanoma patients.