There is a growing body of evidence demonstrating the impacts of human arrival in new “pristine” environments, including terrestrial habitat alterations and species extinctions. However, the effects of marine resource utilization prior to industrialized whaling, sealing, and fishing have largely remained understudied. The expansion of the Norse across the North Atlantic offers a rare opportunity to study the effects of human arrival and early exploitation of marine resources. Today, there is no local population of walruses on Iceland, however, skeletal remains, place names, and written sources suggest that walruses existed, and were hunted by the Norse during the Settlement and Commonwealth periods (870–1262 AD). This study investigates the timing, geographic distribution, and genetic identity of walruses in Iceland by combining historical information, place names, radiocarbon dating, and genomic analyses. The results support a genetically distinct, local population of walruses that went extinct shortly after Norse settlement. The high value of walrus products such as ivory on international markets likely led to intense hunting pressure, which—potentially exacerbated by a warming climate and volcanism—resulted in the extinction of walrus on Iceland. We show that commercial hunting, economic incentives, and trade networks as early as the Viking Age were of sufficient scale and intensity to result in significant, irreversible ecological impacts on the marine environment. This is to one of the earliest examples of local extinction of a marine species following human arrival, during the very beginning of commercial marine exploitation.