Long-term studies of predator food habits (i.e., ‘predator-based sampling’) are useful for identifying patterns of spatial and temporal variability of forage nekton in marine ecosystems. We investigated temporal changes in forage fish availability and relationships to ocean climate by analyzing diet composition of three puffin species (horned puffin Fratercula corniculata, tufted puffin Fratercula cirrhata, and rhinoceros auklet Cerorhinca monocerata) from five sites in the North Pacific from 1978–2012. Dominant forage species included squids and hexagrammids in the western Aleutians, gadids and Pacific sand lance (Ammodytes personatus) in the eastern Aleutians and western Gulf of Alaska (GoA), and sand lance and capelin (Mallotus villosus) in the northern and eastern GoA. Interannual fluctuations in forage availability dominated variability in the western Aleutians, whereas lower-frequency shifts in forage fish availability dominated elsewhere. We produced regional multivariate indicators of sand lance, capelin, and age-0 gadid availability by combining data across species and sites using Principal Component Analysis, and related these indices to environmental factors including sea level pressure (SPL), winds, and sea surface temperature (SST). There was coherence in the availability of sand lance and capelin across the study area. Sand lance availability increased linearly with environmental conditions leading to warmer ocean temperatures, whereas capelin availability increased in a non-linear manner when environmental changes led to lower ocean temperatures. Long-term studies of puffin diet composition appear to be a promising tool for understanding the availability of these difficult-to-survey forage nekton in remote regions of the North Pacific.