The medieval North Atlantic and North Sea was home to an ever-growing panoply of marine monsters, or so it would seem in accounts ranging from early Roman explorers through late medieval Icelandic naturalists. This transdisciplinary paper uses data from zooarchaeology, history, literature, and new approaches to ancient DNA analysis to rebuild changing marine mammal demographics throughout the northern seas. Accounts of marine mammals, including descriptions, behaviors, strandings, and encounters with sailors include important and previously unrecognized data that testifies to changing marine mammal populations from the early Middle Ages, the Medieval Warm Period, and through the Little Ice Age. Accounts from Tacitus (2nd cen.), Adam of Bremen (11th), Konungs Skuggsjá (13th), Olaus Magnus and Adriaen Coenen (16th) and Jon the Learned (early 17th) reveal both resident and transient populations of marine species, reflections of marine paleoclimate change. These textual accounts, when coupled with new isotopic and genetic data, offer a new source of proxy data on marine mammals in medieval northern seas.