While freshwater and anadromous fish have been critical economic resources for late prehistoric and modern Native Americans, the origin and development of fishing is not well understood. We document the earliest known human use of freshwater and anadromous fish in North America by 13,000 and 11,800 years ago, respectively, from primary anthropogenic contexts in central Alaska (eastern Beringia). Fish use appears conditioned by broad climatic factors, as all occurrences but one are within the Younger Dryas chronozone. Earlier Bølling-Allerød and later early Holocene components, while exhibiting similar organic preservation, did not yield evidence of fishing, suggesting that this was a response to changing environmental factors, perhaps reductions in higher ranked resources such as large terrestrial mammals. Late Pleistocene and recent Indigenous peoples harvested similar fish taxa in the region (salmon, burbot, whitefish, and pike). We characterize late Pleistocene fishing in interior Beringia as an important element of broad-spectrum foraging rather than the intensive communal fishing and storage common among recent peoples.