The development of therapeutic methods that can effectively delay tumor growth, inhibit tumor metastases, and protect the host from tumor recurrence still faces challenges. Nanoparticle-based combination therapy may provide an effective therapeutic strategy. Herein, we show that bovine serum albumin (BSA)-bioinspired gold nanorods (GNRs) were loaded with an immunoadjuvant for combined photothermal therapy (PTT) and immunotherapy for the treatment of melanoma. In this work, cetyltrimethylammonium bromide (CTAB)-coated GNRs were successively decorated with polyethylene glycol (PEG) and BSA, and loaded with an immunoadjuvant imiquimod (R837). The synthesized mPEG-GNRs@BSA/R837 nanocomplexes under near-infrared (NIR) irradiation could effectively kill tumors and trigger strong immune responses in treating metastatic melanoma in mice. Furthermore, the nanocomplex-based PTT prevented lung metastasis and induced a strong long-term antitumor immunity to protect the treated mice from tumor recurrence. The nanocomplex-based PTT in combination with immunotherapy may be potentially employed as an effective strategy for the treatment of melanoma and other metastatic cancers.