Highly fibrotic and collagen-rich properties in desmoplastic melanoma (DM) result in an immune-suppressive fibrotic tumor microenvironment (TME) that resists clinical therapies. The different clinical and pathological properties, as compared to conventional melanoma, lead to delayed diagnosis and it is difficult to deliver drugs effectively due to fibrosis. Herein, we designed a chemo-immuno strategy focused on combining vaccination immunotherapy with multi-targeting sunitinib (SUN) nano-therapy to remodel TME and generate a robust immune response and a stronger synergistic anti-cancer effect. This strategy was evaluated side-by-side with non-desmoplastic melanoma and achieved significant improvement in therapeutic efficacy. The combination treatment was also synergistically assessed with the desmoplastic melanoma model. This strategy can remodel the fibrotic immunosuppressive TME and result in a robust cytotoxic T-cell response by reducing the collagen content, normalizing blood vessels, inhibiting tumor-associated fibroblasts and reducing high levels of suppressor immune cells. The modification of fibrotic immunosuppressive TME may serve as a good approach to further enhance immunotherapy for desmoplastic tumors.