Colour traits can be elaborated through sexual selection and have potential to drive reproductive isolation. Male three-spined sticklebacks (Gasterosteus aculeatus) express striking visual signals to attract choosy females during courtship, typically expressed as red carotenoid-based pigmentation on their throat and jaw during the breeding season, along with blue eyes and blue/green flanks. The extent and intensity of red colouration in males have been linked to fitness benefits to females, including body condition, parasite resistance, parental ability and nest defence. In some populations in the Pacific Northwest of North America, male three-spined sticklebacks express melanic nuptial colouration. In these populations, male possess black throats instead of red, and have dark or black bodies. Melanic males are associated with waterbodies that are red-shifted due to the presence of tannins, where the ambient light environment is dominated by long wavelengths. Here we report the first discovery outside North America of melanic populations of threespined sticklebacks on the island of North Uist in the Scottish Hebrides, on the northwest Atlantic coast of Europe. These populations are associated with a hotspot of stickleback morphological diversity and occur in association with red-shifted waterbodies.