Increasing exploitation effort and efficiency have been leading to population declines and extinctions among large marine animals. Understanding the magnitude of such losses is challenging because current baselines about species’ abundances and distributions in the sea were mostly established after humans had started affecting marine populations. For artisanal fisheries, from which written historical records are rarely, if ever, available, approaches based on gathering anecdotal information from fishers’ knowledge are a promising method to know past environmental conditions. We interviewed coastal artisanal fishers, with ages varying from 15 to 85 years, to detect temporal changes in the catch abundance of large fish species, particularly the largetooth sawfish, Pristis pristis, and the goliath grouper, Epinephelus itajara, within Abrolhos Bank, Brazil. Most fishers considered that fishing has led to species depletion. However, older fishers reported significantly more species and larger species as depleted than young fishers. Older fishers caught significantly larger smalltooth sawfish and goliath grouper in the past than younger fishers. The largetooth sawfish has not been caught or sought for more than ten years. Probabilistic tests provided no definitive evidence for local extinction, although the past record of sightings indicates a population decline close to the threshold level for extinction probability. We provide evidence that small-scale artisanal fisheries can decimate the abundance of large coastal fishes, one of those almost to local extinction. Finally, our results suggest that the younger generation is not aware of past ecological conditions, indicating the occurrence of a shifting baseline syndrome among the fishing community.