Development of an effective treatment against advanced tumors remains a major challenge for cancer immunotherapy. We have previously developed a potent mannose-modified lipid calcium phosphate (LCP) nanoparticle (NP)-based Trp2 vaccine for melanoma therapy, but because this vaccine can induce a potent anti-tumor immune response only during the early stages of melanoma, poor tumor growth inhibition has been observed in more advanced melanoma models, likely due to the development of an immune-suppressive tumor microenvironment (TME). To effectively treat this aggressive tumor, a multi-target receptor tyrosine kinase inhibitor, sunitinib base, was efficiently encapsulated into a targeted polymeric micelle nano-delivery system (SUN), working in a synergistic manner with vaccine therapy in an advanced mouse melanoma model. SUN not only increased cytotoxic T-cell infiltration and decreased the number and percentage of MDSCs and Tregs in the TME, but also induced a shift in cytokine expression from Th2 to Th1 type while remodeling the tumor-associated fibroblasts, collagen, and blood vessels in the tumor. Additionally, inhibition of the Stat3 and AKT signaling pathways by SUN may induce tumor cell apoptosis or decrease tumor immune evasion. Our findings indicated that targeted delivery of a tyrosine kinase inhibitor to tumors can be used in a novel synergistic way to enhance the therapeutic efficacy of existing immune-based therapies for advanced melanoma.