Anti-PD1 treatment has improved the survival of metastatic melanoma patients, yet it is unknown which patients benefit from the treatment. In this exploratory study, we aimed to understand the effects of anti-PD1 therapy on the patients’ immune system and discover the characteristics that would result in successful treatment. We collected peripheral blood (PB) samples from 17 immuno-oncology-naïve metastatic melanoma patients before and after 1 and 3 months of anti-PD1 therapy. In addition, matching tumor biopsies at the time of diagnosis were collected for tissue microarray. The complete blood counts, PB immunophenotype, serum cytokine profiles, and tumor-infiltrating lymphocytes were analyzed and correlated with the clinical data. Patients were categorized based on their disease control into responders (complete response, partial response, stable disease > 6 months, N = 11) and non-responders (progressive disease, stable disease ≤ 6 months, N = 6). During therapy, the PB natural killer T (NKT) cell frequency, expression of CD25 and CD45RO on cytotoxic natural killer (NK) cells, and serum CXC chemokine levels were significantly increased in responders. Furthermore, higher age together with age-associated characteristics from PB, lower frequency of PB-naïve CD8 T cells, and elevated levels of serum MCP-4 and OPG were discovered as baseline predictors of treatment response. We therefore propose that in addition to T cells, anti-PD1 treatment is associated with NK- and NKT-cell population dynamics, and that the age-associated characteristics from PB together with older age may contribute to prolonged PFS in anti-PD1-treated melanoma patients.