Understanding the factors which influence foraging behaviour and success in marine mammals is crucial to predicting how their populations may respond to environmental change. The Australian fur seal (Arctocephalus pusillus doriferus, AUFS) is a predominantly benthic forager on the shallow continental shelf of Bass Strait, and represents the greatest biomass of marine predators in south-eastern Australia. The south-east Australian region is experiencing rapid oceanic warming, predicted to lead to substantial alterations in prey diversity, distribution and abundance. In the present study, foraging effort and indices of foraging success and efficiency were investigated in 138 adult female AUFS (970 foraging trips) during the winters of 1998–2019. Large scale climate conditions had a strong influence on foraging effort, foraging success and efficiency. Foraging effort and foraging success were also strongly influenced by winter chlorophyll-a concentrations and sea-surface height anomalies in Bass Strait. The results suggest increasing foraging effort and decreasing foraging success and efficiency under anticipated environmental conditions, which may have population-level impacts.