Marine reserves exhibit increases in targeted fish species, but long-term effects on biodiversity are poorly understood. Factors other than reserve status may affect decadal changes, including environmental change. We examined the fish fauna at the iconic Poor Knights Islands over 4 decades (1974–2016) before and after implementation of a no-take marine reserve in 1998. We document a substantial increase in commercially and recreationally targeted Chrysophrys auratus, which was virtually absent before 1994 but by 2016 had reached up to 11 fish per 500m2 (220 per hectare). There were also large changes to the fish community, including the decline of subtropical and coastal wrasses, some species with no change and others that increased significantly. Many declines occurred >20 years before the arrival of abundant C. auratus, suggesting the changes do not represent a trophic cascade. Furthermore, this normally benthic-feeding fish has adopted a mid-water foraging behaviour targeting planktivorous fish. The increase in C. auratus appears to be linked both to reserve status and catch regulations in the wider region. Overall, the data point to long-term environmental fluctuations from the late 1970s having a negative effect on the abundance of more than half the reef fish species at these islands.