Malignant melanoma is the most harmful type of skin cancer and its incidence has increased in this past decade. Early diagnosis and treatment are urgently desired. In this study, we conjugated picolinamide/nicotinamide with the pharmacophore of 131I-MIP-1145 to develop 131I-iodofluoropicolinamide benzamide (131I-IFPABZA) and 131I-iodofluoronicotiamide benzamide (131I-IFNABZA) with acceptable radiochemical yield (40 ± 5%) and high radiochemical purity (>98%). We also presented their biological characteristics in melanoma-bearing mouse models. 131I-IFPABZA (Log P = 2.01) was more lipophilic than 131I-IFNABZA (Log P = 1.49). B16F10-bearing mice injected with 131I-IFNABZA exhibited higher tumor-to-muscle ratio (T/M) than those administered with 131I-IFPABZA in planar γ-imaging and biodistribution studies. However, the imaging of 131I-IFNABZA- and 131I-IFPABZA-injected mice only showed marginal tumor uptake in A375 amelanotic melanoma-bearing mice throughout the experiment period, indicating the high binding affinity of these two radiotracers to melanin. Comparing the radiation-absorbed dose of 131I-IFNABZA with the melanin-targeted agents reported in the literature, 131I-IFNABZA exerts lower doses to normal tissues on the basis of similar tumor dose. Based on the in vitro and in vivo studies, we clearly demonstrated the potential of using 131I-IFNABZA as a theranostic agent against melanoma.