Spontaneous tumor regression, regression in the absence of therapeutic intervention, can be identified histologically in over 25% of primary cutaneous melanomas at initial diagnosis. A unique subset of T lymphocytes found in areas of regression can be histologically distinguished from tumor-infiltrating T lymphocytes (TIL) found in areas of tumor progression. We call this unique subset of T lymphocytes regression-associated T lymphocytes (RATs). The aim of this study is to determine the phenotype of lymphocytes and the density of specific cell types linked to immunosuppression in areas of tumor progression compared with areas of tumor regression. These specific cell types include T-regulatory cells (Tregs) and S100A9+ cells. A total of 14 primary cutaneous melanomas with areas of progression and regression were used. Immunohistochemistry staining was used to identify CD4+ cells, CD8+ cells, Tregs, and S100A9+ cells. Two independent observers manually counted three high-powered ×40 fields. There was no predominance of CD4+ or CD8+ T lymphocytes in either RATs or TIL. We identified a lower density of Tregs in RATs compared with TIL when using the FOXP3+/CD4+ Treg marker (P=0.04) and a marginal difference when using our second, confirmatory Treg marker, FOXP3+/CD25+ (P=0.11). We observed a lower density of S100A9+ cells in RATs compared with TIL (P=0.002). There was an observable difference in the tumor microenvironments of RATs and TIL, with RATs having a significantly lower density of Tregs and S100A9+ cells. We deduce that the absence of immunosuppression in areas of regression allows for a more robust immune response and thus effective eradication of tumor cells.