The baseline for what is ‘pristine’ or ‘healthy’ ecosystem shifts over time with each new generation in a phenomenon known as ‘shifting baseline syndrome’. The syndrome is particularly important in monitoring and restoration of depleted ecosystems, as such systems often suffer from lack of baseline data on their former pristine state. In this study, 350 fishermen selected randomly from seven fish-landing sites in Tanga, Tanzania, were interviewed for their insights and perceptions on changes in catch size, fishery stock, condition of current fishing grounds, and the number and type of affected groups or species. The majority of fishermen (73%) belonging to older age group perceived that the current size of the fish catch has declined drastically, while only 47% and 19% from the middle and younger age groups, respectively, share the view. The number of fishing grounds identified as depleted differed significantly among the three generations of fishermen (Kruskal Wallis, c2 ¼ 135.689, d.f ¼ 2, p < 0.001), with old, middle-aged and young citing 9, 5 and 2 species, respectively. Additionally, there is significant difference in the number of fishing grounds cited as degraded among the three age groups (p < 0.001). Evidence for decline, mostly from old and middle-aged groups, was also revealed by increasing number of fish species with undesirable characteristics such as toughness of meat and unpleasant flavour, which fishermen used to discard to the sea in the past. In areas where long-term ecological data are missing, fishermen’s local knowledge accumulated over time can reveal modified ecosystems thus recognising temporal scale of problems facing marine fisheries.