Human-induced ecological change in the open oceans appears to be accelerating. Fisheries, climate change and elevated nutrient inputs are variously blamed, at least in part, for altering oceanic ecosystems. Yet it is challenging to assess the extent of anthropogenic change in the open oceans, where historical records of ecological conditions are sparse, and the geographical scale is immense. We developed millennial-scale amino acid nitrogen isotope records preserved in ancient animal remains to understand changes in food web structure and nutrient regimes in the oceanic realm of the North Pacific Ocean (NPO). Our millennial-scale isotope records of amino acids in bone collagen in a wide-ranging oceanic seabird, the Hawaiian petrel (Pterodroma sandwichensis), showed that trophic level declined over time. The amino acid records do not support a broad-scale increase in nitrogen fixation in the North Pacific subtropical gyre, rejecting an earlier interpretation based on bulk and amino acid specific δ15N chronologies for Hawaiian deep-sea corals and bulk δ15N chronologies for the Hawaiian petrel. Rather, our work suggests that the food web structure in the NPO has shifted at a broad geographical scale, a phenomenon potentially related to industrial fishing.