Climate changes in the Arctic are predicted to alter distributions of marine species. However, such changes are difficult to quantify because information on present species distribution and the genetic variation within species is lacking or poorly examined. Blue mussels, Mytilus spp., are ecosystem engineers in the coastal zone globally. To improve knowledge of distribution and genetic structure of the Mytilus edulis complex in the Arctic, we analyzed 81 SNPs in 534 Mytilus spp. individuals sampled at 13 sites to provide baseline data for distribution and genetic variation of Mytilus mussels in the European Arctic. Mytilus edulis was the most abundant species found with a clear genetic split between populations in Greenland and the Eastern Atlantic. Surprisingly, analyses revealed the presence of Mytilus trossulus in high Arctic NW Greenland (77°N) and Mytilus galloprovincialis or their hybrids in SW Greenland, Svalbard, and the Pechora Sea. Furthermore, a high degree of hybridization and introgression between species was observed. Our study highlights the importance of distinguishing between congener species, which can display local adaptation and suggests that information on dispersal routes and barriers is essential for accurate predictions of regional susceptibility to range expansions or invasions of boreal species in the Arctic.