Melanoma are malignant tumors derived from melanocytes being responsible for the majority of skin cancer deaths with an increasing rate of incidence. The Melanocortin-1 receptor (MC1R) has been recognized as a molecular target for melanoma detection. Here, we report on the development and optimization of molecular probes which are based on novel conjugates of near-infrared (NIR) fluorescent indocyanine dyes and an MC1R-targeting peptide intended for optical fluorescence imaging enabling an early, specific, accurate and sensitive diagnosis of malignant melanomas. The introduction of anionic groups into the aromatic ring of the indolenine substructure of the conjugated dyes has shown to result in a strong fluorescence in aqueous solution and a concomitant increase of binding affinities of the peptide conjugates to the target receptor. The length and flexibility of the PEG chain introduced as a linker, as well as the nature of its attachment to the dye also affect the binding affinities, albeit to a lower extent. The conjugates have been successfully applied in the MC1R-specific staining of B16F10 melanoma cells, both in cell cultures and in microtome sections of solid tumors.