The human cutaneous metastatic melanoma is the deadliest skin cancer. Partial, or less frequently complete spontaneous regressions could be observed, mainly mediated by T cells. Nevertheless, the underlying mechanisms are not fully unraveled. We investigated the first events of the immune response related to cancer regression in Melanoma-bearing Libechov Minipigs (MeLiM), a unique swine model of cutaneous melanoma that regresses spontaneously. Using a multiparameter flow cytometry strategy and integrating new clinical and histological criteria of the regression, we show that T cells and B cells are present only in the late stages, arguing against their role in the initial destruction of malignant cells. NK cells infiltrate the tumors before T cells and therefore might be involved in the induction of the regression process. Myeloid cells represent the main immune population within the tumor microenvironment regardless of the regression stage. Among those, MHCII + CD163 − macrophages that differ phenotypically and functionally compared to other tumor-associated macrophages, increase in number together with the first signs of regression suggesting their crucial contribution to initiating the regression process. Our study supports the importance of macrophage reprogramming in humans to improve current immunotherapy for metastatic melanoma.