If we could be transported back through time, would we recognize the structure of ocean ecosystems through the prism of their current state? What have we lost and to what degree might we be able to restore their potential? Historical narratives and descriptions of both natural history and the abundance of marine animals paint a vivid (if fragmented) picture of ocean ecosystems that extend back over millennia. Centuries-old chronicles of early explorers traveling to the New World include numerous tales of the untold bounty of the seas. Historians recognize, however, that it is necessary to treat such descriptions with some care. Were some written to attract investors in fishing and trading enterprises, others to attract settlers to uncharted lands? The History of Marine Animal Populations (HMAP) project of the Census of Marine Life (CoML) program seeks to complement anecdotal reports and historical records with careful analysis of sources such as logbooks of whaling and fishing vessels, tithing or tax archives, and the paleo-ecological record to provide more quantitative estimates of marine animal populations of the past. To establish appropriate restoration goals, it is essential to determine the ocean’s potential productivity. This analysis would permit establishment of realistic baselines for comparison with existing states of nature. Only then can we begin to assess whether appropriate goals are being set. The danger is in setting the bar too low by underestimating the production potential of the seas based on recent rather than historical levels.