Knowledge of the range and chronology of historic trade and long-distance transport of natural resources is essential for determining the impacts of past human activities on marine environments. However, the specific biological sources of imported fauna are often difficult to identify, in particular if species have a wide spatial distribution and lack clear osteological or isotopic differentiation between populations. Here, we report that ancient fish-bone remains, despite being porous, brittle, and light, provide an excellent source of endogenous DNA (15-46%) of sufficient quality for whole-genome reconstruction. By comparing ancient sequence data to that of modern specimens, we determine the biological origin of 15 Viking Age (800-1066 CE) and subsequent medieval (1066-1280 CE) Atlantic cod (Gadus morhua) specimens from excavation sites in Germany, Norway, and the United Kingdom. Archaeological context indicates that one of these sites was a fishing settlement for the procurement of local catches, whereas the other localities were centers of trade. Fish from the trade sites show a mixed ancestry and are statistically differentiated from local fish populations. Moreover, Viking Age samples from Haithabu, Germany, are traced back to the North East Arctic Atlantic cod population that has supported the Lofoten fisheries of Norway for centuries. Our results resolve a long-standing controversial hypothesis and indicate that the marine resources of the North Atlantic Ocean were used to sustain an international demand for protein as far back as the Viking Age.