As the ice cap of the Arctic diminishes due to global warming, the polar sailing route will be open larger parts of the year. These changes are likely to increase the pollution load on the pristine Arctic due to large vessel traffic from specific contaminant groups, such as polycyclic aromatic hydrocarbons (PAHs). A well-documented baseline for PAH concentrations in the biota in the remote regions of the Nordic Seas and the sub-Arctic is currently limited, but will be vital in order to assess future changes in PAH contamination in the region. Blue mussels (Mytilus edulis) were collected from remote sites in Greenland, Iceland, the Faroe Islands, Norway and Sweden as well as from urban sites in the same countries for comparison. Code (Gadus morhua) was caught north of Iceland and along the Norwegian coast. Sixteen priority PAH congeners and the inorganic trace elements arsenic, cadmium, mercury and lead were analyzed in the blue mussel samples as well as PAH metabolites in cod bile. Σ16PAHs ranged from 28 ng/g dry weight (dw) (Álftafjörður, NW Iceland) to 480 ng/g dw (Ísafjörður, NW Iceland). Mussel samples from Mjóifjörður, East Iceland and Maarmorilik, West Greenland, contained elevated levels of Σ16PAHs, 370 and 280 ng/g dw, respectively. Levels of inorganic trace elements varied with highest levels of arsenic in mussels from Ísafjörður, Iceland (79 ng/g dw), cadmium in mussels from Mjóifjörður, Iceland (4.3 ng/g dw), mercury in mussels from Sørenfjorden, Norway (0.23 ng /g dw) and lead in mussels from Maarmorilik, Greenland (21 ng/g dw). 1-OH-pyrene was only found above limits of quantification (0.5 ng/mL) in samples from the Norwegian coast, ranging between 44 and 140 ng/ml bile. Generally, PAH levels were low in mussels from the remote sites investigated in the study, which indicates a limited current effect on the environment.