Melanoma is the most deadly type of skin cancer, constituting annually ∼ 75% of all cutaneous cancer-related deaths due to metastatic spread. Currently, because of metastatic spread, there are no effective treatment options for late-stage metastatic melanoma patients. Studies over the past two decades have provided insight into several complex molecular mechanisms as to how these malignancies evade immunological control, indicating the importance of immune escape or suppression for tumor survival. Thus, it is essential to develop innovative cancer strategies and address immune obstacles with the goal of generating more effective immunotherapies. One important area of study is to further elucidate the role and significance of myeloid-derived suppressor cells (MDSCs) in the maintenance of the tumor microenvironment. These cells possess a remarkable ability to suppress immune responses and, as such, facilitate tumor growth. Thus, MDSCs represent an important new target for preventing tumor progression and escape from immune control. In this study, we investigated the role of MDSCs in immune suppression of T cells in an antigen-specific B16 melanoma murine system utilizing a novel synthetic tyrosinase (Tyr) DNA vaccine therapy in both prophylactic and therapeutic models. This Tyr vaccine induced a robust and broad immune response, including directing CD8 T-cell infiltration into tumor sites. The vaccine also reduced the number of MDSCs in the tumor microenvironment through the downregulation of monocyte chemoattractant protein 1, interleukin-10, CXCL5 and arginase II, factors important for MDSC expansion. This novel synthetic DNA vaccine significantly reduced the melanoma tumor burden and increased survival in vivo, due likely, in part, to the facilitation of a change in the tumor microenvironment through MDSC suppression.