Malignant melanoma is known by its rapid progression and poor response to currently applied treatments. Despite the well-documented melanoma immunogenicity, the results of immunotherapeutic clinical trials are not satisfactory. This poor antitumor reactivity is due to the development of chronic inflammation in the tumor microenvironment characterized by infiltrating leukocytes and soluble mediators, which lead to an immunosuppression associated with cancer progression. Using the ret transgenic mouse melanoma model that closely resembles human melanoma, we demonstrated increased levels of chronic inflammatory factors in skin tumors and metastatic lymph nodes, which correlated with tumor progression. Furthermore, Gr1(+)CD11b(+) myeloid-derived suppressor cells (MDSC), known to block tumor-reactive T cells, were enriched in melanoma lesions and showed an enhanced immunosuppressive capacity. This MDSC accumulation was associated with a strong TCR ζ-chain downregulation in T cells suggesting that the tumor inflammatory microenvironment supports MDSC recruitment and immunosuppressive activity. Indeed, upon administration of phosphodiesterase-5 inhibitor sildenafil or paclitaxel in non-cytotoxic doses, we observed reduced levels of chronic inflammatory mediators in association with decreased MDSC amounts and immunosuppressive function. This led to a partial restoration of ζ-chain expression in T cells and to a significantly increased survival of tumor-bearing mice. CD8 T-cell depletion resulted in an abrogation of beneficial outcome of both drugs, suggesting the involvement of MDSC and CD8 T cells in the observed therapeutic effects. Our data imply that inhibition of chronic inflammation in the tumor microenvironment should be applied in conjunction with melanoma immunotherapies to increase their efficacy.