Melanocytes are pigmented cells residing mostly in the skin and hair follicles of vertebrates, where they contribute to colouration and protection against UV-B radiation. However, the spectrum of their functions reaches far beyond that. For instance, these pigment-producing cells are found inside the inner ear, where they contribute to the hearing function, and in the heart, where they are involved in the electrical conductivity and support the stiffness of cardiac valves. The embryonic origin of such extracutaneous melanocytes is not clear. We took advantage of lineage-tracing experiments combined with 3D visualizations and gene knockout strategies to address this long-standing question. We revealed that Schwann cell precursors are recruited from the local innervation during embryonic development and give rise to extracutaneous melanocytes in the heart, brain meninges, inner ear, and other locations. In embryos with a knockout of the EdnrB receptor, a condition imitating Waardenburg syndrome, we observed only nerve-associated melanoblasts, which failed to detach from the nerves and to enter the inner ear. Finally, we looked into the evolutionary aspects of extracutaneous melanocytes and found that pigment cells are associated mainly with nerves and blood vessels in amphibians and fish. This new knowledge of the nerve-dependent origin of extracutaneous pigment cells might be directly relevant to the formation of extracutaneous melanoma in humans.