Malignant melanoma is a highly aggressive cancer, and the incidence of this disease is increasing worldwide at an alarming rate. Despite advances in the treatment of melanoma, patients with metastatic disease still have a poor prognosis and low survival rate. New strategies, including targeted radiotherapy, would provide options for patients who become resistant to therapies such as BRAF inhibitors. Very late antigen-4 (VLA-4) is expressed on melanoma tumor cells in higher levels in more aggressive and metastatic disease and may provide an ideal target for drug delivery and targeted radiotherapy. In this study, we evaluated 177Lu- and 68Ga-labeled DOTA-PEG4-LLP2A as a VLA-4-targeted radiotherapeutic with a companion PET agent for diagnosis and monitoring metastatic melanoma treatment. DOTA-PEG4-LLP2A was synthesized by solid-phase synthesis. The affinity of 177Lu- and 68Ga-labeled DOTA-PEG4-LLP2A to VLA-4 was determined in B16F10 melanoma cells by saturation binding and competitive binding assays, respectively. Biodistribution of the LLP2A conjugates was determined in C57BL/6 mice bearing B16F10 subcutaneous tumors, while PET/CT imaging was performed in subcutaneous and metastatic models. 177Lu-DOTA-PEG4-LLP2A showed high affinity to VLA-4 with a Kd of 4.1 ± 1.5 nM and demonstrated significant accumulation in the B16F10 melanoma tumor after 4 h (31.5 ± 7.8%ID/g). The tumor/blood ratio of 177Lu-DOTA-PEG4-LLP2A was highest at 24 h (185 ± 26). PET imaging of metastatic melanoma with 68Ga-DOTA-PEG4-LLP2A showed high uptake in sites of metastases and correlated with bioluminescence imaging of the tumors. These data demonstrate that 177Lu-DOTA-PEG4-LLP2A has potential as a targeted therapeutic for treating melanoma as well as other VLA-4-expressing tumors. In addition, 68Ga-DOTA-PEG4-LLP2A is a readily translatable companion PET tracer for imaging of metastatic melanoma.